November 11, 2014 · glc obrada slika

Segmentacija bazirana na teksturama

Slike iz prirodne okoline su najčešće jako kompleksne. Površine različitih objekata mogu biti prekrivene teksturama koje nemaju jasno izražene ivice. Uzmimo za primer koru drveta, keramičke pločice, ljudsku kožu, okean. Njihova struktura je ono što jasno karakteriše izgled površina koje zauzimaju. Poznat je veliki broj metoda za opisivanje i ekstrakciju tekstura, međutim ne postoji jedinstvena definicija teksture kao ni jedinstven matematički model koji bi proizveo teksturu. Kao još uvek potpuno neistražena analiza tekstura predstavlja zanimljivu oblast za naučnike i istraživače koji se bave kompjuterskom vizijom.

Uglavnom na slikama postoji više od jedne teksture. Glavni cilj je na neki način opisati teksturu na osnovu određenih matematičkih mera, izvršiti prepoznavanje a zatim je klasifikovati prema skupu unapred određenih vrednosti/mera u odgovarajuću klasu.

Ekstrakcija osobina tekstura pomoću GLC matrica

GLC matrica (Grey-Level Co-occurrence Matrix) je tabelerna predstava informacija koje se odnose na to koliko često se različite kombinacije osvetljenosti pojavljuju u slici. Primenom metoda GLC matrica moguće je izračunati različite osobine tekstura u određenom regionu slike, nezavisno od slike. Pre nego što krenemo u detaljnu diskusiju o načinu funkcionisanja GLC matrica treba napomenuti da postoje različite metode kojima je moguće izvući različite osobine tekstura. Postoje metodi prvog, drugog, trećeg i viših redova.

  1. Metode prvog reda tekstura su statističke mere koje se mogu izračunati direktno iz slike, neuzimajući u obzir međusobne veze između piksela. Pogodne su za slike koje imaju slučajnu teksturu. Neke od vrednosti koje se mogu izračunati su varijansa, srednja vrednost, devijacija... Kompleksnije metode prvog reda, kao što su momenti, apsolutni momenti, centralni momenti ili entropija, moguće je izračunati preko histograma slike.
  2. Metode drugog reda tekstura imaju svest od vezi u grupama od između dva najčešće susednih piksela.
  3. Metode trećeg i viših redova tekstura (razmatrajući veze između tri i više piksela) su teorijski moguće, ali se ne sreću često u praksi zbog izuzetno velike vremenske zahtevnosti i težine interpretacije.

Nakon kraćeg osvrta na različite metode ekstrakcije tekstura iz slika nastavljamo se opisom funkcionisanja GLC matrica kao pripadnika metoda drugog reda. Svaki element koonkurense matrice predstavlja verovatnoću pojave para tačaka u određenom regionu slike. U daljem razmatranju piksel koji trenutno posmatramo definišemo kao referentni piksel a njegovog suseda kao susedni piksel. Radi lakšeg razumevanja GLC matrica jednostavnim primerom ilustrovaćemo funkcionisanje ovog metoda. Na slici ispod nalazi se primer jednog regiona u okviru slike.

Primer regiona slike

Iteracijom kroz region slike sa leva na desno, svaki piksel u jednom trenutku postaje referentni piksel, počevši od piksela u gornjem levem uglu regiona. Pikseli koji se nalaze uz desnu ivicu nemaju svog suseda pa se ne uzimaju u razmatranje. U okviru ovog posta i prateće implementacije kao rastojanje između dva piksela koristi se korak od jednog piksela.

Pikaz sadržaja GLC matrice

*U zaglavlju kolona priložene tabele nalaze se moguće vrednosti inteziteta susednog piksela. U zaglavlju redova se nalaze vrednosti referentnog piksela. U preseku reda i kolone nalazi se broj ponavljanja tranzicija između susednog i referentnog piksela

Tabela iznad je priložena radi lakšeg razumevanja sadržaja same GLC matrice. Ćelija sa koordinatama (0, 0) se popunjava sa brojem koji označava koliko puta u određenom regionu slike, referentni piksel sa intezitetom 0 ima desnog suseda sa intezitetom 0. Postoji četiri GLC matrice koje pokrivaju susede koji se nalaze pod različitim uglovima u odnosu na referentni.

Izračunavanje osobina tekstura zahteva simetričnu matricu. Sledeći korak je dovođenje matrice u simetričnu formu. Simetrična matrica znači da se iste vrednosti ponavalju na suprotnim stranama u odnosu na dijagonalu, primera radi sadržaj ćelije (1, 2) bi morao biti jednak sadržaju ćelije (2, 1).

Ukoliko bi računali vrednosti samo u jednom smeru, rezultat ne bi bio simetrična matrica. Primer vrednosti dobijenih računanjem ponavaljanja samo u smeru ka istoku

Prikaz sadržaja nakon računanja vrednosti u smeru ka istoku

Ukoliko se brojanje ponavljanja vrši na ovaj način, samo u jednom pravcu, dobijena matrica neće biti simetrična. Vrednosti sa suprotnih strana nisu jednake. Simetrija može biti ostvarena ukoliko se svaki par piksela posmatra u oba pravca, kada je reč o horizonalnoj GLC matrici, levo i desno. Svaka pojava para X1 i X2 inkrementirala bi brojač u dva polja za 1, na lokacijama X1X2 i X2X1. Tako dobijena matrica može se smatrati simetričnom i naziva se horizontalna matrica.

Nakon izračunavanja četiri GLC matrice, po jedna za svaku orijentaciju 0̊, 45̊, 90̊ i 135̊ potrebno je izvršiti normalizaciju vrednosti u tabelama. Mere osobina tekstura zahtevaju da broj u ćeliji bude verovatnoća ponavaljanja a ne samo broj. Kako bi izračunali verovatnoću potrebno je vrednost svake ćelije podeliti sa brojem ukupnih ponavaljanja vrednosti tabele.

Opšti pojam verovatnoće može se definisati kao “broj ponavljanja nekog događaja, podeljen ukupnim brojem mogućih ishoda”.

Normalizaciju GLC tabele na osnovu prethodne definicije možemo predstaviti pomoću sledeće formule (gde i predstavlja red, a j kolonu)

Ukratko gore opisani koraci za dobijanje simetrične normalizovane GLC matrice se mogu opisati sledećim koracima:

  1. Kreirati GLC matrice po jedna za svaku orijentaciju 0̊, 45̊, 90̊ i 135̊
  2. Dimenzije matrice jednake su broju nijansi sive u posmatranoj slici
  3. U svaku ćeliju upisati broj ponavaljanja
  4. Dobijenoj matrici sabrati sa svojom transponovanom verzijom kako bi se dobila simetrična matrica.
  5. Normalizacija vrednosti u GLC matrice kako bi se generisale verovatnoće za svaki ishod

GLC matrice imaju isti broj redova i kolona kao kvantizacioni nivo slike. To znači da je za jednu 8bitnu grayscale sliku potrebna kvadratna matrica dimenzija 256x256, sa 65 536 ćelija. Ukoliko bi ulazna slika imala 16bitni podatak o nijansi sive, dimenzije GLC matrice bi iznosile 65 536x65 536 što bi ukupno dalo 429 496 720 ćelija. Primećuje se da veći nivo detalja slike uključuje znatno veći broj iteracija.

Određen broj aplikacija žrtvuje nivo detalja slike zarad manjeg procesorskog opterećenja, pa se 8 bitne slike često pretvaraju u 4 bitne (16x16 matrica sa 256 ćelija). Postoji još jedan razlog za degradaciju kvaliteta i kompresiju podatka o intezitetu slike. Ukoliko se koriste sve ćelije matrice dimenzija 256x256, veliki broj ćelija imao bi vrednost nula. GLC matrice posmatraju verovatnoće između dva piksela, pa bi veliki broj nula u tabeli doprineo lošoj aproksimaciji. Ukoliko je broj sivih nijansi u slici smanjen, smanjuje se i broj nultih vrednosti u tabeli, pa se i statistička validnost znatno poboljšava.

Nakon kreiranja i incijalizacije GLC matrica potrebno je izvući korisne informacije, statističke podatke o teksturama. Rezultat računanja pojedinačne osobine teksture je broj koji opisuje region slike. Osobine se mogu podeliti u tri grupe. Prva grupa sadrži metode bazirane na kontrastu, a to su : Kontrast, Homogenost i Raznolikost. Druga grupa predstavlja metode koje opisiju uređenost tekstura : energija i entropija. Metode ove grupe pokazuju koliko je neka tekstura regularna u okviru klizećeg prozora. Metode korelacije mere linearnu zavisnost sivih nivoa susednih piksela

Priložene su jednačine za ekstrakciju osobina tekstura :

Entropija: Entropija daje meru kompleksnosti slike. Kompleksne teksture uglavnom imaju veću entropiju.

Kontrast: Kontrast je mera kontrasta slike, preciznije količine lokalnih varijacija u intezitetu posmatrane slike.

Homogenost: Homogenost je osobina teksture suprotna kontrastu.

Energija: --

Na kraju prilažem i implementaciju metode za ekstrakciju osobina tekstura.

 // Author: Stankovic Vlada svlada@gmail.com
 public class FeatureExtractorGLCM 
 {
     private int dw;
     private int dh;

     private int nW;
     private int nH;

     private int height;
     private int width;

     public BufferedImage img;

     public double [][] featureMatrix;
     public double [][] glcm0, glcm45, glcm90, glcm135;

     public FeatureExtractorGLCM(BufferedImage p_img, int p_dw, int p_dh)
     {
         img = p_img;
         height = p_img.getHeight();
         width = p_img.getWidth();

         dw = p_dw;
         dh = p_dh;

         this.prepareImage(p_img);

         // nW*nH Total number of feature vectors
         // Every feature vector consists of six features
         // rowMin, rowMax, colMin, colMax, Homogenity, Contrast
         // featureMatrix = new double[nW*nH][20];
         // glcm matrixes for all orientations of image
         glcm0 = new double[256][256];
         glcm45 = new double[256][256];
         glcm90 = new double[256][256];
         glcm135 = new double[256][256];
     }
     //16,8
     public FeatureExtractorGLCM(BufferedImage p_img)
     {
         this(p_img, 50, 50);
     }

     public LinkedList glcmWindow()
     {

         return null;
     }
     /**
      * Extend image size if there is need, if block size is unstandard
      * @param p_img
      * @return
      */
     public BufferedImage prepareImage(BufferedImage p_img)
     {
         int newWidth = width;
         int newHeight = height;

         if ((newWidth % dw) != 0)
         {
             newWidth = width + (dw-(width%dw));
         }

         if ((newHeight % dh) != 0)
         {
             newHeight = height + (dh-(height%dh));
         }

         BufferedImage filteredImage = new BufferedImage(newWidth, newHeight, BufferedImage.TYPE_INT_RGB);

         for (int row = 0; row < height; row++)
         {
             for (int column = 0; column < width; column++)
             {
                 int pixVal = ImgUtil.getRGBPixel(img, column, row);
                 ImgUtil.setRGBPixelByValue(filteredImage, column, row, pixVal);
             }
         }

         height = newHeight;
         width = newWidth;

         nW = width/dw;
         nH = height/dh;

         featureMatrix = new double[nW*nH][20];

         img = filteredImage;
         return filteredImage;
     }

     public void calculateGLCM(int p_row, int p_col)
     {
         int offsetX = 0,    
             offsetY = 0;

         int i2 = 0, 
             j2 = 0;

         int pixCnt0     = 0, 
             pixCnt45    = 0,    
             pixCnt90    = 0, 
             pixCnt135   = 0;

         for (int i = p_row; i < p_row+dh; i++)
         {
             for (int j = p_col; j < p_col+dw; j++)
             {
                 // Generation of GLC, angle 0
                 offsetX = 1;
                 offsetY = 0;
                 // komsijski pixel
                 i2 = i + offsetX; 
                 j2 = j + offsetY;

                 if (i2 < height && i2 > -1 && j2 > -1 && j2 < width )
                 {
                     int referencePix = ImgUtil.getRed(img, j, i);
                     int neiPix = ImgUtil.getRed(img, j2, i2);
                     glcm0[referencePix][neiPix]++;
                     glcm0[neiPix][referencePix]++;
                     pixCnt0+=2;
                 }

                 // Generation of GLC, angle 45 
                 offsetX = 1;
                 offsetY = 1;
                 // Neighbourh pixel
                 i2 = i + offsetX; 
                 j2 = j + offsetY;

                 if (i2 < height && i2 > -1 && j2 > -1 && j2 < width )
                 {
                     int referencePix = ImgUtil.getRed(img, j, i);
                     int neiPix = ImgUtil.getRed(img, j2, i2);
                     glcm45[referencePix][neiPix]++;
                     glcm45[neiPix][referencePix]++;
                     pixCnt45+=2;
                 }

                 //  Generation of GLC, angle 90
                 offsetX = 0;
                 offsetY = 1;
                 // Neighbourh pixel
                 i2 = i + offsetX; 
                 j2 = j + offsetY;

                 if (i2 < height && i2 > -1 && j2 > -1 && j2 < width )
                 {
                     int referencePix = ImgUtil.getRed(img, j, i);
                     int neiPix = ImgUtil.getRed(img, j2, i2);
                     glcm90[referencePix][neiPix]++;
                     glcm90[neiPix][referencePix]++;
                     pixCnt90+=2;
                 }

                 // Generation of GLC, angle 135
                 offsetX = 0;
                 offsetY = 1;
                 // Neighbourh pixel
                 i2 = i + offsetX; 
                 j2 = j + offsetY;

                 if (i2 < height && i2 > -1 && j2 > -1 && j2 < width )
                 {
                     int referencePix = ImgUtil.getRed(img, j, i);
                     int neiPix = ImgUtil.getRed(img, j2, i2);
                     glcm135[referencePix][neiPix]++;
                     glcm135[neiPix][referencePix]++;
                     pixCnt135+=2;
                 }
             }// end_for j
         }//end_for i

         // GLC Normalization
         for (int i = 0; i < 256; i++)
         {
             for (int j = 0; j < 256; j++)
             {
                 glcm0[i][j] /= pixCnt0;
                 glcm45[i][j] /= pixCnt45;
                 glcm90[i][j] /= pixCnt90;
                 glcm135[i][j] /= pixCnt135; 
             }
         }
     }


     public void populateFeatureMatrix()
     {
         double mean = calculateMean(img);
         double dev = calculateStandardDeviation(img, mean);
         System.out.println("dev " + dev);
         int cnt = 0;
         double maxDev = 0;
         for (int i = 0; i < height; i+=dh)
         {
             for (int j = 0; j < width; j+=dw)
             {   
                 this.calculateGLCM(i, j);

                 featureMatrix[cnt][0] = featureCalcMean(i, j);
                 featureMatrix[cnt][1] = featureCalcDeviation(i, j, mean);

                 if (featureMatrix[cnt][1] > maxDev) maxDev = featureMatrix[cnt][1];

                 double [] feat = featureCalcContrast();

                 featureMatrix[cnt][2] = feat[0];
                 featureMatrix[cnt][3] = feat[1];
                 featureMatrix[cnt][4] = feat[2];
                 featureMatrix[cnt][5] = feat[3];

                 feat = featureCalcHomogeneity();

                 featureMatrix[cnt][6] = feat[0];
                 featureMatrix[cnt][7] = feat[1];
                 featureMatrix[cnt][8] = feat[2];
                 featureMatrix[cnt][9] = feat[3];

                 feat = featureCalcEnergy();

                 featureMatrix[cnt][10] = feat[0];
                 featureMatrix[cnt][11] = feat[1];
                 featureMatrix[cnt][12] = feat[2];
                 featureMatrix[cnt][13] = feat[3];

                 if 

                 (   
                     // Homogenity
                     /*
                     featureMatrix[cnt][6] > 0.5 && featureMatrix[cnt][6] < 1 && 
                     featureMatrix[cnt][7] > 0.5 && featureMatrix[cnt][7] < 1 &&
                     featureMatrix[cnt][8] > 0.5 && featureMatrix[cnt][8] < 1 && 
                     featureMatrix[cnt][9] > 0.5 && featureMatrix[cnt][9] < 1 &&
                     featureMatrix[cnt][1] > maxDev/3

                      &&
                     featureMatrix[cnt][13] > 0.001 && featureMatrix[cnt][13] < 0.1 
                     featureMatrix[cnt][11] > 0.001 && featureMatrix[cnt][11] < 0.1 
                     &&
                     */

                     featureMatrix[cnt][10] > 1 && featureMatrix[cnt][10] < 5 &&

                     featureMatrix[cnt][12] > 1 && featureMatrix[cnt][12] < 5

                 )
                 {               
                     for (int y = i; y < i+dh; y++)
                     {
                         if (y < height && y > -1)
                             ImgUtil.setRGBPixelByRGB(img, 0xff, 255, 0, 0, j, y);
                     }
                     for (int y = i+dh-1; y < i+dh; y++)
                     {
                         if (y < height && y > -1)
                             ImgUtil.setRGBPixelByRGB(img, 0xff, 255, 0, 0, j, y);
                     }

                     for (int x = j; x < j+dw; x++)
                     {
                         if (x < width && x > -1)
                             ImgUtil.setRGBPixelByRGB(img, 0xff, 255, 0, 0, x, i);
                     }
                     for (int x = j+dw-1; x < j+dw; x++)
                     {
                         if (x < width && x > -1)
                             ImgUtil.setRGBPixelByRGB(img, 0xff, 255, 0, 0, x, i);
                     }

                 }
                 cnt++;
             }
         }
         try 
         {
             FSUtil.dumpToHtml(featureMatrix, "c:\\feature.html");
         } 
         catch (IOException e) { e.printStackTrace();}
         //FSUtil.dumpMatrixToTxt(featureMatrix, "Feature Matrix");
     }

     /**
         Returns a measure of the intensity contrast between a pixel and its neighbor over the whole image.
         Range = [0 (size(GLCM,1)-1)^2] 
         Contrast is 0 for a constant image.
     */
     public double[] featureCalcContrast()
     {
         double retVal0 = 0,
               retVal45 = 0,
               retVal90 = 0,
               retVal135 = 0;

         for (int i = 0; i < glcm0.length; i++)
         {
             for (int j = 0; j < glcm0[0].length; j++)
             {
                 retVal0 += Math.abs(i - j)*Math.abs(i - j)  * glcm0[i][j];
                 retVal45 += Math.abs(i - j)*Math.abs(i - j) * glcm45[i][j]; 
                 retVal90 += Math.abs(i - j)*Math.abs(i - j) * glcm90[i][j]; 
                 retVal135 += Math.abs(i - j)*Math.abs(i - j)* glcm135[i][j]; 
             }
         }
         return new double[] {retVal0, retVal45, retVal90, retVal135};
     }

     /**
      *  
         Returns a value that measures the closeness of the distribution of elements in the GLCM to the GLCM diagonal.
         Range = [0 1]
         Homogeneity is 1 for a diagonal GLCM.
      **/
     public double[] featureCalcHomogeneity()
     {
         double retVal0 = 0,
               retVal45 = 0,
               retVal90 = 0,
               retVal135 = 0;

         for (int i = 0; i < glcm0.length; i++)
         {
             for (int j = 0; j < glcm0[0].length; j++)
             {
                 retVal0 += glcm0[i][j] / (1 + Math.abs(i - j)); 
                 retVal45 += glcm45[i][j] / (1 + Math.abs(i - j)); 
                 retVal90 += glcm90[i][j] / (1 + Math.abs(i - j)); 
                 retVal135 += glcm135[i][j] / (1 + Math.abs(i - j)); 
             }
         }
         return new double[] {retVal0, retVal45, retVal90, retVal135};
     }

     /**     
         Returns the sum of squared elements in the GLCM.
         Range = [0 1]
         Energy is 1 for a constant image.
      */
     public double[] featureCalcEnergy()
     {       
         double retVal0 = 0,
               retVal45 = 0,
               retVal90 = 0,
               retVal135 = 0;

         for (int i = 0; i < glcm0.length; i++)
         {
             for (int j = 0; j < glcm0[0].length; j++)
             {
                 retVal0 += Math.pow(glcm0[i][j], 2);
                 retVal45 += Math.pow(glcm45[i][j], 2);
                 retVal90 += Math.pow(glcm90[i][j], 2); 
                 retVal135 += Math.pow(glcm135[i][j], 2); 
             }
         }

         return new double[]{retVal0, retVal45, retVal90, retVal135};
     }

     public double featureCalcMean(int p_row, int p_col)
     {
         double retVal = 0;  
         for (int y = p_row; y < p_row+dh; y++)
         {
             for (int x = p_col; x < p_col+dw; x++)
             {
                 retVal+=ImgUtil.getRed(img, x, y);  
             }
         }
         retVal = retVal/(height*width);
         return retVal;
     }

     public double featureCalcDeviation(int p_row, int p_col, double p_mean)
     {
         double retVal = 0;  
         for (int y = p_row; y < p_row+dh; y++)
         {
             for (int x = p_col; x < p_col+dw; x++)
             {
                 int pixel = ImgUtil.getRed(img, x, y);
                 retVal += Math.abs((int)p_mean - pixel);
             }
         }
         retVal = retVal/(height*width);
         return retVal;
     }

     // Mean
     public static double calculateMean(BufferedImage p_img)
     {
         double retVal = 0;
         int height = p_img.getHeight();
         int width = p_img.getWidth();

         for (int row = 0; row < height; row++)
         {
             for (int column = 0; column < width; column++)
             {
                 retVal+=ImgUtil.getRed(p_img, column, row);
             }
         }
         retVal = retVal/(height*width);
         return retVal;
     }
     // Standard deviation
     public static double calculateStandardDeviation(BufferedImage p_img, double p_mean)
     {
         double retVal = 0;
         int height = p_img.getHeight();
         int width = p_img.getWidth();

         for (int row = 0; row < height; row++)
         {
             for (int column = 0; column < width; column++)
             {
                 int pixel = ImgUtil.getRed(p_img, column, row);
                 retVal += Math.abs((int)p_mean - pixel);
             }
         }
         retVal = retVal/((height*width));
         return  (double) retVal;
     }

     public void printMatrix(double [][] p_Matrix)
     {
         for (int i = 0; i < p_Matrix.length; i++)
         {
             for (int j = 0; j < p_Matrix[0].length; j++)
             {
                 System.out.print(" | " + p_Matrix[i][j]);
             }
             System.out.println();
         }
     }
 }

Follow me on Twitter

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket
Comments powered by Disqus