RSS Feed

Seam Carving (3)

Zupdatowałem źródło projekciku Seam Carving.

Troszeczkę przesadziłem z designem aplikacji. No ale od czegoś trzeba zacząć. Już wiem z czym to się je.

Aplikacja Rozdzielona jest na trzy moduły.

-UI w Formsach
-Silnik Algorytmu
-Silnik Graficzny

Silnik Graficzny:


IEnergyCalculator: – interfejs klasy liczącej energię
EnergyCalGradient – liczenie gradientu
IImageProcessor – interfejs klasy przetwarzającej obraz
GdiImageProcess – przetwarzanie przy pomocy GDI+ i LockBitów
IPixelManipulator – interfejs klasy modyfikującej pixele
PixelColor -kolorowanie pixeli
PixelRemove – usuwanie pixeli

Silnik Algorytmu


ISeamManipulator : – interfejs klasy operującej na Seamach
DynamicSeamManipulator – dynamiczne usuwanie seama
DynamicSeamManipulatorWithMark – to samo ale z zaznaczaniem seama
StaticSeamManipulator – statyczne seamy [nie obsługiwane]
StaticSeamManipulatorWithMark

Read the rest of this entry »

Advertisements

Seam Carving (2)

Po dłuższej przerwie postanowiłem ostro wziąć się do roboty za algorytm skalowania obrazków. Jest już ładna formatka [szczyt ui designu] i parę opcji. Skalowanie statycznym seamem tzn po lini prostej i skalowanie dynamicznym seamem tzn wyszukiwanie najlepszej drogi. Wszystko jak na razie działa przy pionowym skalowaniu ale wkrótce zmontuje skalowanie poziome. Pierw muszę troszeczkę przeprojektować aplikację bo wdarł się lekki chaos do kodu i kod jest “be” a ja nie na widzę brzydkiego kodu 😛

Przeprojektowałem znacznie aplikację , zrefaktoryzowałem kod dla lepszej czytelności i dorzuciłem interfejsy w celu zmniejszenia zależności pomiędzy klasami i wyeliminowania z duplikowanego kodu zgodnie z zasadą DRY = “Don’t repeat Yourself” ;]. Jeszcze jeden interfejs nie jest do końca dorobiony i przemyślany bo nie wiem jak pogodzić zabawę na wskaźnikach w klasie z modyfikatorem “unsafe” … coś wymyślę ;]

Aplikacja opiera się teraz na 2 interfejsach.

    9     public interface IImageProcessing

   10     {

   11         void Open();

   12         void Close();

   13 

   14         void SetBmp(Bitmap bmp);

   15         Bitmap GetBmp();

   16         void SaveBmp(string fileLocation);

   17 

   18         void RemoveStaticRow(int x);

   19         void RemoveDynamicRow(int[] inTab);

   20         void MarkDynamicRow(int[] inTab);

   21         void MarkStaticRow(int x);

   22 

   23         int[,] Gradient(bool saveBmp);

   24     }

IImageProcessing definiuje nasz silnik graficzny na którym będziemy operować i jego metody do obróbki obrazu.
W tym momencie mam jedną klasę implementująca ten interfejs GDIImageProces. Dzięki takiemu rozdzieleniu interfejsów od implementacji Klasa SeamCarving nie zastanawia się nad tym co się dzieje przy obróbce obrazu i mogę łatwo podmienić silnik graficzni np na wolniejszy korzystający z metod GetPixel SetPixel. Wystarczy ze stworzę nową klasę i zaimplementuje odpowiednie metody interfejsu IImageProcessing. Jest to bodajże pewna implementacja wzorca Strategia “Policy”.

   10     public interface IManipulator

   11     {

   12         void ManipulateSeam(IImageProcessing imgProcessor);

   13     }

IManipulator definiuje algorytmy przetwarzania Seamow wyszcególniam 4 rodzaje tych algorytmów:
– Statyczne usuwanie Seama bez zaznaczania czerwoną kreską
– Statyczne usuwanie Seama z zaznaczaniem
– Dynamicznie usuwanie bez zaznaczania
– Dynamicznie usuwanie z zaznaczaniem

W tym momencie rozdzielone mam 2 metody wyjściowe jedną przyjmująca obiekt implementujący IManipulatora z zaznaczaniem i drugą bez zaznazczania. Wkrótce postaram się znaleźć jakieś lepsze rozwiązanie by była jedna metoda. A nie 2 przyjmujące podobny obiekt. Wprowadza to pewne “confusion” dla usera który nie do końca wie jak z tych metod skorzystać. Jest to spowodowane tym że musiałem zastosować śmieszne obejście błedu w GDI+ poprzez dwukrotne clonowanie bitmap.

   82             Bitmap tmp = (Bitmap)_imgProcessor.GetBmp().Clone();

   83 

   84             SeamManipulation(seamManipulator, numberOfOper);

   85 

   86             Bitmap tmp1 = (Bitmap)_imgProcessor.GetBmp().Clone();

   87             _imgProcessor.SetBmp(tmp);

Znalazłem na razie zastępczą metodę dla kolorowania składni. Add-in do visuala Copy Source As Html


Dynamiczny Seam

Rysunek po obróbce 150+ seamów.

Wrzuciłem kod źródłowy wersji “alpha” do działu Projekciki . Podaje tam także linka do mojego repozytorium Svn-owego. Proszę się nie śmiać z komentarzy :]


Optymalizacja Grafu

Na mojej kochanej PWR realizowałem prostą implementację grafu z wyszukiwaniem najkrótszych ścieżek w grafie. Trochę się zirytowałem gdy mój cudowny kod chodził 20 razy wolniej ;] od kodu kolegi. Niestety moja chorobliwa ambicja nie odpuściła i postanowiłem zoptymalizować kod …..

Zabawę zacząłem z programikiem dotTrace który jest świetnym profilerem badającym wydajność programów. Fajną sprawą jest wyświetlanie ilości wywołań poszczególnych metod i czas ich trwania. Dzięki temu z łatwością możemy wydzielić bloki kodu w których najprawdopodobniej powinniśmy optymalizować. Zgodnie z zasadą 20/80 zmiana 20% najbardziej czasochłonnych linii kodu da 80% wzrost wydajności.

Po analizie i paru zmianach okazało się że źle przeprowadzałem testy. Zamiast ciągle operować na tym samym elemencie za każdym razem tworzyłem nową instancję klasy odpowiedzialnej za algorytm. Przy 1 Milionie wywołań algorytmu dawało to długi czas działania aplikacji po lekkiej modyfikacji czas wykonania spadł z 60 s do 320ms.

Conclusion:
Pamiętajmy o odpowiednim konstruowaniu testów 😛

Ciekawy jest także fakt że tak naprawdę czas wykonania mojego programu zajmuje tylko 56% czasu działania aplikacji. 44% pożerają procedury .netowe


Seam Carving (1) – Content aware image scaling algorithm

I m developing a great algorithm at my University ,  Wroclaw University of Technology. Seam Carving is a idea of Shai Avidan and Ariel Shamir.

This Algorithm is scaling the image by defining and erasing the least significant parts of the image. This way the main and most important content of the image is untouched. I will show you this simple idea on this example.

Image used to the testing process (Sky Tower in Wroclaw)

 

Energy image

 

Algorithm is looking for the place with the lowest energy sum.

 

One of the fragments selected to remove from the image. Those fragments are called seams.

 

Original picture after one hundreds seams removed

 

Notice the weird blue car. At the moment this is a very simple implementation. But we can see that main part of the image The Towers are untouched by the algorithm.