Artykuł przedstawia implementacje algorytmu sluzacego do wykrywania krawędzi, ktory jest oparty na zbiorach rozmytych.
Fuzzy Edge Detection in C#, czyli algorytmy wykrywania krawędzi oparte na zbiorach rozmytych.
Algorytmy wykrywania krawędzi są ciągle przedmiotem badań wielu naukowców w wyniku, czego istniej ich bardzo wiele. Ale najlepsze efekty dają algorytmy oparte na zbiorach rozmytych, choć potrzebują znacznie więcej obliczeń, a czasami nawet parę razy trzeba „przechodzić” po badanych obrazie.
W tym artykule przedstawię algorytm „Image edge detection using Fuzzy Classiefier”. Algorytm ten składa się z 4 podstawowych kroków:
Krok 1: ustawienie podanych przez użytkownika trzech parametrów low, high i ? (omega, na rysunku oznaczony jest on symbolem )
Krok 2: dla każdego piksela policz różnice miedzy jego ośmioma sąsiadami i zapisz w wektorze.
Krok 3: Dla każdego wektora policz wartość funkcji przynależności, określającej, do której klasy należy piksel.
Krok 4: Na podstawie reguł rozmytych, jeżeli to określ czy dany piksel jest tłem, czy krawędzią.
Co to jest zbiór rozmyty wyjaśniłem w poprzednim artykule „Fuzzy Image Processing in C#, czyli algorytmy przetwarzania obrazów oparte na zbiorach rozmytych”. Ale również i tym razem nie obejdzie się od wprowadzenie teoretycznego.
Żeby móc zając się implementacją algorytmów służących do wykrywania krawędzi musimy zdefiniować sobie parę pojęć.
Sąsiedztwo piksela:
Pierwszym krokiem tego algorytmu jest wyliczenie dla danego piksela na rys piksel P5 wektora: X=[X1,X2,X3,X4,X5,X6,X7,X8], gdzie:
X1 = P1 - P5; X2 = P2 - P5
X3 = P3 - P5; X4 = P4 - P5
X5 = P6 - P5; X6 = P7 - P5
X7 = P8 - P5; X8 = P9 - P5
Klasa tła i krawędzi:
Gdy już mamy policzony wektor X dla danego piksela musimy wyliczyć wartość dwóch funkcji przynależności dla klasy tła oraz krawędzi i na tej podstawie stwierdzić czy piksele jest krawędzią, czy tłem. Krawędź najłatwiej jest rozpoznać, jeżeli występuje duże rocznice pomiędzy badanym pikselem a jego sąsiadami, co prawda może być to tez szum, dlatego często przed wykrywaniem krawędzi obraz filtruje się w celu wyeliminowania szumów, choć istnieją algorytmy oparte na zbiorach rozmytych usuwające szumy. (np. Competitive Fuzzy Edge Detection). Wartość funkcji przynależności dla klasy tła i krawędzi oblicza się następująco:
Klasa tła:
Klasa krawędzi:
, gdzie
Jak łatwo zauważyć te funkcje przyjmuj wartości z przedziału [0;1].
Klasyfikacje do danej klasy przedstawia poniższy rysunek:
Wyliczanie wartości nowego piksela:
Gdy już mamy wyliczone wartość funkcji przynależności dla ww. klas możemy popijać decyzje czy badany piksel jest tłem czy krawędzią. Posłużą nam do tego następujące reguł, JEŻELI – TO:
JEŻELI Klasa tła ma większą wartość funkcji przynależności TO zmień piksel na biały
JEŻELI Klasa krawędzi ma większą funkcji przynależności TO zmień piksel na czarny
JEŻELI wartości te są równe TO zmień piksel na biały
Po wstępie teoretycznym przystąpmy do implementacji tego algorytmu C#, którą rozpoczniemy od klasy algorytmu EdgeDetectionWithFuzzyClassifier i wyposażymy ją w metody służące do wykonania wszystkich potrzebnych obliczeń.
public class EdgeDetectionWithFuzzyClassifier
{
Bitmap newBitmap;
Color newPixelColor;
double []fuzzyTruths;
int []featureVector;
double Gray, Gray1;
int []ft1;
int []ft2;
int f1, f2;
int low, high, omega;
public EdgeDetectionWithFuzzyClassifier()
{
//
// TODO: Add constructor logic here
//
this.newPixelColor = new Color();
featureVector = new int[8];
fuzzyTruths = new double[2];
ft1 = new int [8];
ft2 = new int [8];
low = 6;
high = 15;
omega = 80000;
}
Zmienne ft1 i ft2 służą do przechowywania wyników pośrednich przy wyliczaniu tzw. fuzzyTruth, która była zdefiniowana powyżej. Powyżej kolei zmienne low i high to składowe wektorów i .
Żeby zaoszczędzić sobie obliczeń nie będziemy działać na modelu RGB, ale na YUV, a dokładniej na samej składowej Y, bo pikselowi przypisujemy wartość 0 lub 255 (czyli czarny lub biały). Do tego celu przyda nam się funkcja, wyliczy nam wartość składowej Y na podstawie składowych R,G,B:
public double CalculateY(int R, int G, int B)
{
double Y;
return Y = (0.299*R) + (0.587*G) + (0.114*B) + 0.5;
}
Jak wspomniałem pierwszym krokiem algorytmu jest wyliczenie wektora X zw. featureVector. Odpowiedzialna ze to będzie poniższa metoda.
public void CalculateFeatureVector(Bitmap bitmap, int x, int y)
{
int pos = 0;
Gray = CalculateY (bitmap.GetPixel(x,y).R, bitmap.GetPixel(x,y).G, bitmap.GetPixel(x,y).B);
for(int i = -1; i < 2; i++)
for (int j = -1; j < 2; j++)
{
if( !(i==0&&j==0) )
{
Gray1 = CalculateY(bitmap.GetPixel(x+j,y+i).R, bitmap.GetPixel(x+j,y+i).G,
bitmap.GetPixel(x+j,y+i).B);
featureVector[pos] = (int)Math.Abs(Gray - Gray1);
pos++;
}
}
}
Przyjmuje ona trzy argumenty obraz wejściowy bitmap, oraz współrzędne badanego piksela x i y. Wynikiem jej działania jest wektor, który zawiera różnice pomiędzy badanym pikselem a jego ośmioma sąsiadami.
Gdy już pierwszy krok algorytmu mamy za sobą możemy przejść dalej. Potrzebujemy teraz metody, które na podstawie wyliczonego wektora wylicza wartość funkcji przynależności (zw. fuzzyTruths) dla dwóch klas: tła i krawędzi. Funkcja obliczająca wartość dla klasy tła wygląda tak:
public void CalculateBackgroundClass()
{
if ((featureVector[0]<=low) && (featureVector[1]<=low)
&& (featureVector[2]<=low) && (featureVector[3]<=low)
&& (featureVector[4]<=low) && (featureVector[5]<=low)
&& (featureVector[6]<=low) && (featureVector[7]<=low) )
fuzzyTruths[0] = 1;
else
{
for (int i=0; i < 8; i++)
ft1[i] = (int)Math.Abs(featureVector[i] - low);
f1 = 0;
f2 = 0;
for (int i = 0; i < 8; i++)
f1 += (int)Math.Pow(ft1[i],2.0);
// fuzzy truth1
fuzzyTruths[0] = CalculateFuzzyTruthValue(f1);
}
}
A to funkcja obliczająca fuzzyTruths dla klasy tła:
public void CalculateEdgeClass()
{
if ((featureVector[0]>=high) && (featureVector[1]>=high)
&& (featureVector[2]>=high) && (featureVector[3]>=high)
&& (featureVector[4]>=high) && (featureVector[5]>=high)
&& (featureVector[6]>=high) && (featureVector[7]>=high) )
fuzzyTruths[1] = 1;
else
{
for (int i=0; i < 8; i++)
ft2[i] = (int)Math.Abs(featureVector[i] - high);
f2 = 0;
for (int i = 0; i < 8; i++)
f2 += (int)Math.Pow(ft2[i],2);
// fuzzy truth1
fuzzyTruths[1] = CalculateFuzzyTruthValue(f2);
}
}
W ciałach obu funkcji wywoływana jest metoda CalculateFuzzyTruth oblicza ona wartość funkcji przynależności, którą zdefiniowaliśmy przy okazji omawiania klasy tła i krawędzi i jest postaci: a jako argument przyjmuje wartość wyrażenia, pod wartością bezwzględną.
public double CalculateFuzzyTruthValue(double X)
{
double fuzzyTruth = 1 - X / Math.Pow(omega, 2.0);
if (fuzzyTruth > 0)
return fuzzyTruth;
else
return 0.0;
}
W momencie, gdy już mamy wszystkie funkcje pomocnicze możemy zająć się całością algorytmu. Sprawa już jest prosta.
public Bitmap Algorithm(Bitmap bitmap)
{
int x,y;
newBitmap = new Bitmap(bitmap.Width, bitmap.Height );
for (y = 1; y < bitmap.Height - 1; y++ )
for (x=1; x < bitmap.Width-1; x++)
{
CalculateFeatureVector(bitmap, x, y);
CalculateEdgeClass();
CalculateBackgroundClass();
if (fuzzyTruths[0]>=fuzzyTruths[1])
Gray = 255;
else
Gray = 0;
newPixelColor = Color.FromArgb((int)Gray,(int)Gray,(int)Gray);
newBitmap.SetPixel(x,y,newPixelColor); }
return newBitmap;
}
W ten oto sposób mamy zaimplementowany algorytm służący do wykrywania krawędzi oparty na zbiorach rozmytych. Omawiany przeze mnie algorytm jest stosunkowy prosty, gdyż użyte funkcje przynależności nie sa zbyt skomplikowane jak np. w algorytmie Competitive Fuzzy Edge Detection, gdzie mamy aż pięć klas krawędzi i jedna tła i dla inna funkcje przynależności, co znacznie komplikuje implementacje algorytmu i wykracza poza ramy niniejszego artykułu.
Poniżej zamieszczone są rysunki prezentujące działanie opisane algorytmu.
A to przykładowe efekty uzyskane omawianym algorytmem:
Obraz oryginalny: obraz z wykrytymi krawędziami
low = 6, high = 15, omega = 80000
Literatura:
[1] MICROSOFT .NET SDK Tool Developer’s Documentation (Common Language Infrastructure)
[2] MSDN
[3] Lily Rui Liang, Carl G. Looney, “Competitive fuzzy edge detection”
Applied Soft Computing 3 (2003) 123–137
[4] J.C. Russ, "The Image Processing Handbook", CRC Press, USA, 1994.
[5] Home Page of Professor Carl G. Looney http://ultima.cs.unr.edu:80/index.php
[6] Homepage of Fuzzy Image Processing http://watfor.uwaterloo.ca/tizhoosh/
[7] Homepage of Hamid R. Tizhoosh http://pami.uwaterloo.ca/tizhoosh/
Załączniki: