Category Archives: C++

Kamerka jako kontroler… Czemu nie? [Kod w C++]

Już myślałem, że nie pamiętam hasła; dawno mnie tu nie było. Ale spoko, do rzeczy.

Kinect, Move i inne tego typu technologie dotarły pod strzechy. Osobiście nie jestem posiadaczem żadnego z nich, jednak gdy mam okazję, to lubię powygłupiać się przed kamerką i na przykład poudawać, że odbijam piłeczkę ping-pongową. Grałem raz na jakiś czas, nie zastanawiając się jak to do końca działa.

Pewnego popołudnia na jednym z laboratoriów bawiliśmy się biblioteką OpenCV, która to służy do przetwarzania obrazów. Na początku przetwarzanie plików JPG, odszumianie tła, wykrywanie krawędzi obiektów itp – wszystko za pomocą gotowych funkcji okazało się być bardzo prostą sprawą.

Potem przyszedł czas na eksperymenty z przetwarzaniem w locie. Obraz kamerki dostarczany i analizowany klatka po klatce, obrabiany za pomocą tych samych funkcji, które były używane do operacji na obrazkach JPG. Fajna sprawa.

A teraz krótkie pytanie i szybka odpowiedź: Jak zrobić prosty kontroler ruchu? Bardzo łatwo! Mianowicie, bierzemy kawałek jednokolorowego kartonu (taki wielkości kartki A5) i rysujemy na nim dwa dowolne, ale identyczne kształty (można wydrukować i nakleić na karton). W moim przypadku kwadraty. Kontroler gotowy! Teraz czas na nieco bardziej skomplikowaną część softwareową. Najpierw należy pobrać i skonfigurować bibliotekę OpenCV – sporo tutoriali dla różnych systemów operacyjnych znajdziecie w sieci, więc nie będę tutaj opisywał jak to zrobić. Po wszystkim odpalamy ulubiony edytor/IDE/cokolwiek w czym możemy pisać programy w C++ (ponoć C# też się nada, ale osobiście nie próbowałem). I do dzieła!

W dalszej części pominę szczegóły. Może zachęcę Was w ten sposób do czytania dokumentacji ;]

Najpierw podpinamy kamerkę do zmiennej:

CvCapture* capture = cvCaptureFromCAM(CV_ANY_CAP);

Następnie w nieskończonej pętli (lub skończonej jakimś sygnałem/klawiszem/timeoutem) odczytujemy kolejne klatki przesłane z kamerki:

IplImage* frame = cvQueryFrame(capture);

Teraz za pomocą bibliotecznych funkcji działamy na obiekcie frame – pozbywamy się szumów, niepożądanych małych elementów oraz rysujemy krawędzie znalezionych obiektów. Ja używam do tego funkcji cvErode, cvDilate, cvSmooth i cvCanny. Po wstępnej obróbce otrzymujemy obrazek z wyróżnionymi krawędziami obiektów.
Teraz wypada wyróżnić kontury, które łączą się ze sobą tworząc jakieś wielokąty. Do tego celu używamy funkcji cvFindContours, która odpowiednio wywołana (znów odsyłam do dokumentacji) utworzy listę kształtów na obrazie. Iterując sobie po kształtach szukamy narysowanego przez nas kształtu. Jak go rozpoznać? Tu przychodzi z pomocą statystyka i momenty Hu, o których polecam poczytać na Wikipedii. Generalnie są to wartości jednoznacznie identyfikujące kształt, które nie są czułe na pochylenie i obrót danego kształtu. Słowem – jeśli znamy pierwsze 2 momenty Hu naszego obiektu, to jeśli poprawnie rozpoznamy jego kontury, niezależnie od położenia określimy, że to jest nasz obiekt. Do wyznaczania momentów Hu istnieje funkcja cvGetHuMoments (ładnie opisana w dokumentacji). Ok, wszystko pięknie, mamy rozpoznane milijon obiektów na obrazie, wyznaczone ich momentyHu i inne pierdy, ale nie wiemy jak określić te wartości dla narysowanych przez nas na kartonie figur. Są dwie drogi – pierwsza, zapewne stosowana na UAMie, to liczenie ich ręcznie; druga – przystawienie wzorca tak blisko kamerki, że rozpozna ona tylko jeden obiekt i wypisze jego momenty Hu na konsoli. Wybór należy do Was.
Screenshot mojego dzieła.
Finiszujemy! Teraz wystarczy sprawdzić, czy w danej klatce znaleźliśmy 2 obiekty o zadanym momencie Hu. Jeśli tak, to w dowolny sposób liczymy dla nich jakąś wartość będącą punktem – najlepiej środek ciężkości. Układamy równanie prostej przechodzącej przez owe środki ciężkości (jeśli nie wiesz jak to zrobić, to zmień zainteresowania informatyczne na zbieranie kasztanów). Do jakiejś zmiennej typu zmiennoprzecinkowego podstawiamy wartość współczynnika kierunkowego prostej. Możemy obliczyć arcustangens od tej wartości i w ten sposób otrzymamy kąt nachylenia naszego kontrolera.
Prawda, że proste? Jak doprowadzę do porządku kod mojego programu, to go tutaj dorzucę, aktualnie napawajcie się opisem.
A na koniec kilka Hintów:

  1. Kontroler musi być dość sztywny, żeby był równo oświetlany i niepotrzebnie się nie zaginał.
  2. Obiekty na kontrolerze powinny być proste (kwadraty, koła, trójkąty); co prawda zdarzało się, że rozpoznawanym przez mój system elementem kontrolera był włącznik światła na ścianie lub karton stojący na szafie, ale i to można łatwo obejść definiując minimalny rozmiar obiektu.
  3. Kontroler powinien mieć duży kontrast – najlepiej czarne obiekty na białym tle.
  4. Nie ma złotego środka na określenie parametrów metod odszumiających obrazek. Trzeba działać metodą odkrywkową.
  5. Moje rozwiązanie nie jest doskonałe i potrafi być zależne od ilości światła padającego na kontroler 😦
  6. Przy rozpoznawaniu obiektów pod uwagę można brać tylko pierwszy moment Hu lub dwa pierwsze.
  7. Należy unikać operatorów równościowych przy porównaniu momentu Hu oczekiwanego z momentem Hu obiektu. Najlepiej założyć sobie margines błędu rzędu 0.01 i sprawdzać, czy różnica między bieżącym momentem Hu a danym jest mniejsza od 0.01 i wtedy zaklasyfikować obiekt jako rozpoznany.
  8. Warto zdefiniować przed pętlą dwa liczniki – ilość ramek rozpoznanych i ilość wszystkich ramek. W ten sposób możemy po wyjściu z pętli określić jaka część klatek została prawidłowo rozpoznana. Jeśli wynik sięgnie 30% to jest dobrze, 50% – wybitnie, 70% – tyle wyciąga Move produkowany przez pewną znaną japońską firmę. Moje wyniki po kilku optymalizacjach dotarły do 65%, więcej nie dałem rady.

To tyle, życzę powodzenia.

Kod w C++ dla leniwych:

#include <opencv/cv.h>
#include <opencv/highgui.h>
#include <iostream>
#include <string>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <sys/time.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define OBJB1 0.1665 // pierwszy
#define OBJB2 0.0004 // drugi
#define OBJB3 0.0001 // trzeci moment Hu dla kwadratu

using namespace std;

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

	CvCapture* capture = cvCaptureFromCAM(0);

	cvNamedWindow("afterEffects", CV_WINDOW_AUTOSIZE);

	CvScalar colorB = CV_RGB( 0, 255, 0 );

	int minimalnaWielkosc = 10000, pole = 0;
	float iloraz = 1;

	while (1) {

		IplImage* frame = cvQueryFrame(capture);

		frame = ContrastBrightness(frame, 70, 40);

		minimalnaWielkosc = (640 / 12) * (480 / 12);

		IplImage *kopia = cvCreateImage(cvSize(640, 480), IPL_DEPTH_8U, 1);

		cvFlip(frame, frame, 2);

		cvCvtColor(frame, kopia, CV_RGB2GRAY);

		cvSmooth(kopia, kopia, CV_GAUSSIAN, 11, 11, 2, 2);
		cvCanny(kopia, kopia, 10, 60, 3);

		CvMemStorage* storage = cvCreateMemStorage(0);
		CvSeq* contour = 0;
		cvFindContours(kopia, storage, &contour, sizeof(CvContour),
				CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE);

		bool elem1 = 0;
		int rX1 = 0, rY1 = 0;

		for (int i = 0; contour != 0; contour = contour->h_next, i++) {

			static CvMoments* moments = new CvMoments();
			cvMoments(contour, moments);
			static CvHuMoments* huMoments = new CvHuMoments();
			cvGetHuMoments(moments, huMoments);

			CvRect r = cvBoundingRect(contour, 1);

			iloraz = (float) (abs(r.width - r.height))
					/ (float) max(r.width, r.height);

			pole = r.width * r.height;

			if ((pole > minimalnaWielkosc) && (iloraz < 0.4)
					&& (abs(huMoments->hu1 - OBJB1) < 0.5)
					&& (abs(huMoments->hu2 - OBJB2) < 0.005)) { // kwadrat

				cvDrawContours(frame, contour, colorB, colorB, CV_FILLED);

				if (elem1 == 0) {

					elem1 = 1;
					rX1 = r.x;
					rY1 = r.y;

				}

				if ((elem1 == 1)
						&& ((abs(rY1 - r.y) > 50) || ((abs(rX1 - r.x) > 50)))) {

					double a = ((double) (rY1 - r.y)) / ((double) (rX1 - r.x));
					a = atan(a);
					std::cout << a * 180 / 3.14 << endl;

					sendAngle(a*1.3); // zaimplementuj funkcje wysyłającą wartość do jakiegoś urządzenia/pliku/po sieci/...

					elem1 = 0;

				}

			}

			cvReleaseMemStorage(&storage);

		}

		cvShowImage("afterEffects", frame);

		cvReleaseImage(&kopia);
		cvReleaseImage(&frame);

		if ((cvWaitKey(10) & 255) == 27) { // Wciśnięcie ESC kończy działanie programu

			break;

		}

	}

	cvReleaseCapture(&capture);
	cvDestroyWindow("mywindow");
	cvDestroyWindow("afrerEffects");

	return 0;
}

Największa klika w grafie

Projekt z Optymalizacji Kombinatorycznej. NP-trudny; z optymalnym rozwiązaniem ciężko. Pomysłów sporo, złożoności różne, nie zawsze adekwatne do jakości rozwiązań. Wybór padł na najszybszy. Trafnie – łatwa implementacja, czasy poszukiwań króciutki, wyniki powyżej 60% optymalnych rozwiązań, w wielu przypadkach optymalne. Może kiedyś się przyda, więc piszę jak to działa. Żeby nie pisać od nowa, cytuję fragment pracy (całej zamieścić nie mogę).

Etap I – sortowanie
Pierwszy etap działania algorytmu to sortowanie wektora zawierającego opisy wierzchołków.
Wektor sortowany jest malejąco, kluczem sortowania jest natomiast stopień wierzchołka.
Celem sortowania jest ustalenie, który wierzchołek ma największy stopień, ponieważ będzie to
najlepszy kandydat na „podstawę”, od której zaczniemy budowanie kliki. Wynika to z naszego
założenia, że im więcej krawędzi prowadzi do tego wierzchołka (czyli im większy jego stopień),
tym większe prawdopodobieństwo, że to na nim opiera się największa klika istniejąca w grafie
(ponieważ ma najwięcej sąsiadów).

Etap II – rozbudowa kliki
Mając wybrany wierzchołek o najwyższym stopniu przystępujemy do budowy kliki. Umieszczamy
go w nowej strukturze danych (w naszym przypadku wektorze, choć lista jednokierunkowa też
byłaby dobrym pomysłem).
Kolejno sprawdzamy elementy znajdujące się w posortowanym wektorze dalej, niż wybrany
wcześniej wierzchołek. Jeśli wierzchołek jest sąsiadem wierzchołka, na którym budujemy klikę, to
powiększamy ją o nowy wierzchołek i przechodzimy do kolejnego. Jeśli nie jest sąsiadem
„podstawy” to po prostu przechodzimy dalej.
Dodając kolejne wierzchołki postępujemy podobnie, z tym, że dodajemy je do kliki wtedy i tylko
wtedy, gdy są one sąsiadami wszystkich wierzchołków znajdujących się już w klice. Czynność
powtarzamy do czasu „zużycia” wszystkich wierzchołków.
Przy dodawaniu nie są brane pod uwagę wierzchołki, których stopień jest mniejszy od rozmiaru
aktualnie znalezionej kliki (ponieważ nie ma szans, by miały wspólną krawędź z wszystkimi
znajdującymi się już w klice).

Łatwo zauważyć kwadratową złożoność algorytmu. Jeśli ktoś byłby chętny, gotów jestem udostępnić fragmenty kodów w C++ oraz wyniki przeprowadzonych testów efektywnościowych.

O wyższości NetBeans nad Eclipse

Tak, to znowu ja (szczerze, spodziewał się ktoś innej osoby?). Chciałbym wyrzucić swoje żale dotyczące najpopularniejszego wśród Linuksowców IDE jakim jest Eclipse.

Jestem świeżo po instalacji nowego systemu (Ubuntu, bo jakby inaczej) i zbieram się do kupy. Dość wolno. Wczoraj stwierdziłem, że zbliża się kolejny semestr studiów, parę projektów będzie (nie tylko tych związanych z zaliczaniem zajęć) i zainstalowałem sprawdzonego i polecanego Eclipse. Ok, jest fajno, 200MB paczek z apt-get ściągniętych, zainstalowanych, otwieram Eclipsa, wszystko ładnie pięknie. Domyślna perspektywa to Java, zatem szybkie System.out.println( „Hello World” ); – działa, jest fajnie. Ale z uwagi na to, że więcej tworzę w C++ dorzuciłem moduł od tego, przełączyłem perspektywę, no i się zaczęło…

Milijon komunikatów o błędach, brakowało paczek, errorlog rósł szybciej od wszechświata i zanim napisałem tutaj Hello World, ważył chyba z 5 MB. Ok, przeinstalowałem z poziomu Eclipse wszystkie dodatki – to samo. Ściągnąłem paczki ręcznie, doinstalowałem. Trochę się poprawiło, ale losowo pojawiające się okienka z błędami mnie nieco wkurzały. Przekopałem pół google’a, próbowałem wszystkiego, co znalazłem. Dupa.

Z całego rozgoryczenia i zdenerwowania wywaliłem całego Eclipse na zbity interfejs. Odpaliłem Synaptica, wpisałem w wyszukiwarkę „IDE”. I w oczy rzucił mi się NetBeans. Nazwę słyszałem, spytałem Google’a o opinię. Dużo pozytywów, mało problemów. Pobrałem, zainstalowałem, śmiga wszystko! Działa rewelacyjnie, szybko jak na taki kombajn, rewelacyjnie podpowiada kod, zbratał się z Projektantem Qt4. Żyć, nie umierać. Polecam!