In this quick and dirty article, we will be describing a syntax and implementing the new syntax in postgresql backend. The syntax to be implemented is CORRESPONDING clause, which is referenced in the SQL20nn standard draft as "Feature F301, CORRESPONDING in query expressions".

CORRESPONDING clause can be seen as a modifier for set operations in SELECT statements. It filters the projected columns to either match the same column names, or match the column names with a list (CORRESPONDING BY).

Note: [] denotes optionality

query1 and query2 are select statements.

 

query1 UNION     [ ALL ] [ CORRESPONDING [ BY ( column_list ) ] ] query2

query1 EXCEPT    [ ALL ] [ CORRESPONDING [ BY ( column_list ) ] ] query2

query1 INTERSECT [ ALL ] [ CORRESPONDING [ BY ( column_list ) ] ] query2

• CORRESPONDING returns all columns that are in both query1 and query2 with the same name.
• CORRESPONDING BY returns all columns in the column_list that are also in both query1 and query2 with the same name.

We will use UNION operator, INTERSECT and EXCEPT works the same with CORRESPONDING clause. Here are some examples to clarify what CORRESPONDING means.

SELECT 1 a, 2 b, 3 c UNION CORRESPONDING SELECT 4 a, 5 b, 6 c;
 a | b | c
---+---+---
 1 | 2 | 3
 4 | 5 | 6
(2 rows)

Now the fun part, we have removed column b from query2:

SELECT 1 a, 2 b, 3 c UNION CORRESPONDING SELECT 4 a, 6 c;
 a | c
---+---
 1 | 3
 4 | 6
(2 rows)

SELECT 1 a, 2 b, 3 c UNION CORRESPONDING SELECT 4 d;
ERROR:  UNION queries with a CORRESPONDING clause must have

 at least one column with the same name

The idea with CORRESPONDING is, unmatched columns are removed. If no columns left to project, then it is a syntax error.

For the CORRESPONDING BY(column_list) part, one more step of filtering is done to ensure that columns in the column_list are present in query1 and query2.

SELECT 1 a, 2 b, 3 c UNION CORRESPONDING BY(a, b, c) SELECT 4 a, 5 b, 6 c;
 a | b | c
---+---+---
 1 | 2 | 3
 4 | 5 | 6
(2 rows)

We remove a column name from column_list:

SELECT 1 a, 2 b, 3 c UNION CORRESPONDING BY(a, c) SELECT 4 a, 5 b, 6 c;
 a | c
---+---
 1 | 3
 4 | 6
(2 rows)

Although we can suggest that CORRESPONDING BY is more useful with * queries as in:

SELECT * FROM t1 UNION CORRESPONDING BY (a, b) SELECT * FROM t2;

Why

There is a single main reason why I pursued to write a patch for CORRESPONDING in postgresql, I decided to delve into postgresql code base with a simple project and it was in the TODO list. As it turns out it is not simple, and I cannot go without the saying "If it is in the TODO list, it ain’t simple".

Development Environment

After setting up a vmware virtual machine with Pardus Linux installed, complete all the updates and make sure you have at least the following software configuration.

• Pardus Linux 2011.2 (kernel 2.6.37.6 i686 GNU/Linux)
• gcc 4.5.3 (compiler)
• flex 2.5.35 (lexer)
• bison 2.4.3 (parser generator)
• autotools
• gdb
• ccache (compiler cache)
• git (version control)
• eclipse CDT (IDE)

For eclipse configuration please see: http://wiki.postgresql.org/wiki/Working_with_Eclipse

For other details about setting up an environment for postgresql development, please see http://wiki.postgresql.org/wiki/Developer_FAQ

How

In this section, we will touch to the very basics of postgres query execution relating to the execution of a set operation(UNION, INTERSECT, EXCEPT)

1. Parser
   1. Raw Parser – Generate a raw parse tree from the sql statement.
   2. Analyzer – Generate a query tree from a raw parse tree. (This is what we will modify mostly)
2. Optimizer – Choose an efficient plan.
3. Executor – Execute the chosen plan.

How Exactly

There are two simple paths of implementing the CORRESPONDING clause, one is modifying the query tree such that query1 and query2 are wrapped in subqueries, and the other is modifying the way that UNION works which is a big deal involving many parts of the code from analyzer to optimizer. We chose to implement it by modifying the query tree which I will describe in a moment.

1. Modify parser to accept new syntax.
   1. Introduce keywords.
   2. Generate a relevant parse tree for the set operation.
   3. Add metadata about CORRESPONDING operation to node structures in the raw parse tree. (column_list, is it CORRESPONDING or CORRESPONDING BY, etc.)
2. Update analyzer to process the new syntax.
   1. While processing the set operation, verify validity of the CORRESPONDING semantics.
      1. Does the columns exist in both tables
      2. Is there any non-existent column names in column_list.
      3. Is output projection non-empty, etc.
   2. If CORRESPONDING clause is valid, modify query1 and query2.
3. Write documentation.
4. Write regressions.

New Syntax

Modifying parser is the easiest part, you would think. What is the big deal? We are only going to add a keyword, what could go wrong? Well, keep on.

backend/parser/gram.y

gram.y is a bison grammar file. Bison produces a c file from this input. It’s syntax is intuitive and you will feel familiar if you check a few SQL statements you know by heart and inspect their gram.y counterparts. For the hasty it gram.y looks like this:

GrantStmt:	GRANT privileges ON privilege_target TO grantee_list
			opt_grant_grant_option
				{
					GrantStmt *n = makeNode(GrantStmt);
					n->is_grant = true;
					n->privileges = $2;
					n->targtype = ($4)->targtype;
					n->objtype = ($4)->objtype;
					n->objects = ($4)->objs;
					n->grantees = $6;
					n->grant_option = $7;
					$$ = (Node*)n;
				}
		;

Here, uppercase words are keywords, lower case words are further definitions. statement between {} is the raw parse tree description of GrantStmt. privileges, privilege_target, grantee_list, opt_grant_grant_option are defined below this definition of GrantStmt.

Between the curly braces, we refer to the positional arguments of the statement.

n->privileges = $2;

$2 refers to privileges in the first line for example.

Adding CORRESPONDING to gram.y

To use CORRESPONDING BY as a valid clause, we need to add CORRESPONDING and BY keywords to the parser. BY keyword is already used in GROUP BY, ORDER BY etc. so we only need to add CORRESPONDING token.

*** 498,504 ****
  	CHARACTER CHARACTERISTICS CHECK CHECKPOINT CLASS CLOSE
  	CLUSTER COALESCE COLLATE COLLATION COLUMN COMMENT COMMENTS COMMIT
  	COMMITTED CONCURRENTLY CONFIGURATION CONNECTION CONSTRAINT CONSTRAINTS
! 	CONTENT_P CONTINUE_P CONVERSION_P COPY COST CREATE
  	CROSS CSV CURRENT_P
  	CURRENT_CATALOG CURRENT_DATE CURRENT_ROLE CURRENT_SCHEMA
  	CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE
--- 499,505 ----
  	CHARACTER CHARACTERISTICS CHECK CHECKPOINT CLASS CLOSE
  	CLUSTER COALESCE COLLATE COLLATION COLUMN COMMENT COMMENTS COMMIT
  	COMMITTED CONCURRENTLY CONFIGURATION CONNECTION CONSTRAINT CONSTRAINTS
! 	CONTENT_P CONTINUE_P CONVERSION_P COPY CORRESPONDING COST CREATE
  	CROSS CSV CURRENT_P
  	CURRENT_CATALOG CURRENT_DATE CURRENT_ROLE CURRENT_SCHEMA
  	CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE

Add CORRESPONDING to select statement as a valid clause.

*** 8489,8507 ****
  					n->fromClause = list_make1($2);
  					$$ = (Node *)n;
  				}
! 			| select_clause UNION opt_all select_clause
  				{
! 					$$ = makeSetOp(SETOP_UNION, $3, $1, $4);
  				}
! 			| select_clause INTERSECT opt_all select_clause
  				{
! 					$$ = makeSetOp(SETOP_INTERSECT, $3, $1, $4);
  				}
! 			| select_clause EXCEPT opt_all select_clause
  				{
! 					$$ = makeSetOp(SETOP_EXCEPT, $3, $1, $4);
  				}
  		;

  /*
   * SQL standard WITH clause looks like:
--- 8490,8514 ----
  					n->fromClause = list_make1($2);
  					$$ = (Node *)n;
  				}
! 			| select_clause UNION opt_all opt_corresponding_clause select_clause
  				{
! 					$$ = makeSetOp(SETOP_UNION, $3, $4, $1, $5);
  				}
! 			| select_clause INTERSECT opt_all opt_corresponding_clause select_clause
  				{
! 					$$ = makeSetOp(SETOP_INTERSECT, $3, $4, $1, $5);
  				}
! 			| select_clause EXCEPT opt_all opt_corresponding_clause select_clause
  				{
! 					$$ = makeSetOp(SETOP_EXCEPT, $3, $4, $1, $5);
  				}
  		;

Now we need to define opt_corresponding_clause.

 opt_corresponding_clause:
 			CORRESPONDING BY '(' expr_list ')'		{ $$ = $4; }
 			| CORRESPONDING							{ $$ = list_make1(NIL); }
 			| /*EMPTY*/								{ $$ = NIL; }
 			;

We have modified the parameter list of makeSetOp. Let’s go over there.

*** 12642,12648 ****
  }

  static Node *
! makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg)
  {
  	SelectStmt *n = makeNode(SelectStmt);

--- 12649,12655 ----
  }

  static Node *
! makeSetOp(SetOperation op, bool all, List *correspondingClause, Node *larg, Node *rarg)
  {
  	SelectStmt *n = makeNode(SelectStmt);

***************
*** 12650,12655 ****
--- 12657,12663 ----
  	n->all = all;
  	n->larg = (SelectStmt *) larg;
  	n->rarg = (SelectStmt *) rarg;
+ 	n->correspondingClause = correspondingClause;
  	return (Node *) n;
  }

Now we have used SelectStmt->correspondingClause, let’s add that to parsenodes.h

include/nodes/parsenodes.h
***************
*** 1006,1011 ****
--- 1006,1013 ----
  	/*
  	 * These fields are used only in "leaf" SelectStmts.
  	 */
+ 	List	   *correspondingClause;  /* NULL, list of CORRESPONDING BY exprs, or */
+ 	 	 	 	 	 	 	 	/* lcons(NIL, NIL) for CORRESPONDING */

Code will compile, but there is one tidbit missing. Postgres will shout an error to you about unrecognized keywords if you use a CORRESPONDING query.

You have to add all new keywords to kwlist.h

*** 94,99 ****
--- 94,100 ----
  PG_KEYWORD("continue", CONTINUE_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("conversion", CONVERSION_P, UNRESERVED_KEYWORD)
  PG_KEYWORD("copy", COPY, UNRESERVED_KEYWORD)
+ PG_KEYWORD("corresponding", CORRESPONDING, UNRESERVED_KEYWORD)
  PG_KEYWORD("cost", COST, UNRESERVED_KEYWORD)
  PG_KEYWORD("create", CREATE, RESERVED_KEYWORD)
  PG_KEYWORD("cross", CROSS, TYPE_FUNC_NAME_KEYWORD)

At this point we can compile postgres and see that it dismisses the CORRESPONDING or CORRESPONDING BY from a query without an error.

Adding meaning to CORRESPONDING, in analyze.c

In transformSetOperationTree function, we determine the output column names, and verify their existence in tables of both sides. Here CORRESPONDING part is given. CORRESPONDING BY is similar.

 		else if(linitial(stmt->correspondingClause) == NULL)
 		{
 			// CORRESPONDING clause, find matching column names from both tables. If there are none then it is a syntax error.

 			Query	*largQuery;
 			Query	*rargQuery;
 			List	*matchingColumns;

 			/* Analyze left query to resolve column names. */
 			largQuery = parse_sub_analyze((Node *) stmt->larg, pstate, NULL, false);

 			/* Analyze right query to resolve column names. */
 			rargQuery = parse_sub_analyze((Node *) stmt->rarg, pstate, NULL, false);

 			/* Find matching columns from both queries. */
 			matchingColumns = determineMatchingColumns(largQuery->targetList,
 													   rargQuery->targetList);

 			op->correspondingColumns = matchingColumns;
 			op->hasCorrespondingBy = false;

 			/* If matchingColumns is empty, there is an error. At least one column in the select lists must have the same name. */
 			if(list_length(matchingColumns) == 0)
 			{
 				ereport(ERROR, (errcode(ERRCODE_SYNTAX_ERROR),
 								errmsg("%s queries with a CORRESPONDING clause must have at least one column with the same name",
 								context)));
 			}

 			// Create subquery for larg, selecting column names from matchingColumns.
 			stmt->larg = createSubqueryForCorresponding(matchingColumns, stmt->larg);

 			// Assign newly generated query to original left query.
 			op->larg = transformSetOperationTree(pstate, stmt->larg,
 												 false,
 												 <argetlist);

 			// Create subquery for rarg, selecting column names from matchingColumns.
 			stmt->rarg = createSubqueryForCorresponding(matchingColumns, stmt->rarg);

 			// Assign newly generated query to original right query.
 			op->rarg = transformSetOperationTree(pstate, stmt->rarg,
 												 false,
 												 &rtargetlist);
 		}

To create a subquery with given column names and a query to me used as a subquery, we use createSubqueryForCorresponding function. This function returns a SelectStmt for the following statement:

SELECT outputColumns FROM (main_arg)

  /*
  * Returns a subquery selecting outputColumns from main_arg.
  * main_arg is modified and returned.
  */
 static SelectStmt *
 createSubqueryForCorresponding(List* outputColumns, SelectStmt* main_arg)
 {
 	ColumnRef *cr;
 	ResTarget *rt;
 	SelectStmt *n;

 	RangeSubselect * rss;
 	ListCell* mctl;

 	n = makeNode(SelectStmt);
 	n->targetList = NIL;
 	foreach(mctl, outputColumns)
 	{
 		TargetEntry *mctle = (TargetEntry *) lfirst(mctl);

 		cr = makeNode(ColumnRef);
 		cr->fields = list_make1(makeString(mctle->resname));
 		cr->location = -1;

 		rt = makeNode(ResTarget);
 		rt->name = NULL;
 		rt->indirection = NIL;
 		rt->val = (Node *)cr;
 		rt->location = -1;

 		n->targetList = lappend(n->targetList, rt);
 	}

 	rss = makeNode(RangeSubselect);

 	// XXX makeAlias alias name should be empty??
 	rss->alias = makeAlias("", NULL);
	rss->subquery = (Node *)main_arg;

 	n->fromClause = list_make1(rss);

 	main_arg = n;

 	return main_arg;
 }

Documentation and Regression

For documentation, please see changes in

• doc/src/sgml/queries.sgml
• doc/src/sgml/sql.sgml

For regression, please see the excellent article from postgresql, and see the changes in

• src/test/regress/sql/corresponding_union.sql
• src/test/regress/serial_schedule
• src/test/regress/parallel_schedule
• src/test/regress/expected/corresponding_union.out

The (not) part

This is the main reason the patch was not accepted by postgresql mailing list community. When we modify the parse tree in the analyzer.c, we modify it for good. Optimizer, planner, executor never sees a CORRESPONDING clause, they only see the subquery we generated.

=# CREATE VIEW v1 AS SELECT 1 a, 2 b, 3 c UNION CORRESPONDING BY(a, c) SELECT 4 a, 5 b, 6 c;
CREATE VIEW
=# select * from v1;
 a | c
---+---
 1 | 3
 4 | 6
(2 rows)

=# select * from pg_views WHERE viewname = 'v1';
 schemaname | viewname | viewowner |                                                                  definition
------------+----------+-----------+----------------------------------------------------------------------------------------------------------------------------------------------
 public     | v1       | kerem     | SELECT alias.a, alias.c FROM (SELECT 1 AS a, 2 AS b, 3 AS c) alias UNION SELECT alias.a, alias.c FROM (SELECT 4 AS a, 5 AS b, 6 AS c) alias;
(1 row)

Patch File

• Download: corresponding_clause_v4.patch Note: Base for the patch is git commit version 6f3dc00.
• Mailing list reference: pgsql-hackers

Android telefonları için UTM, Derece Dakika Saniye, Ondalık Derece koordinat dönüşüm programı.

Android Market’ten indirmek için (ücretsiz): KorTrans aratabilir veya https://market.android.com/details?id=com.dissipatedheat.kortrans adresine doğrudan gidebilirsiniz.

Desteklediği Koordinat Türleri:

• Universal Transverse Mercator (UTM, 6 derecelik, WGS84 datumu): 35T 555555 4600000
• Derece Dakika Saniye (DDS, DMS): 41° 32′ 59,05″ K 27° 39′ 58,08″ D
• Ondalık Derece (DD): 41,549735 K 27,666134 D

Özellikler:

• Pafta bulma.
• Noktaları kaydedebilme
• Kayıtlı noktalara simge, kod, not ve resim ekleyebilme.
• Kayıtlı noktalar üzerinde manuel veya haritadan sürükleyerek oynama yapabilme
• Kayıtlı noktaların resmini silebilme, değiştirebilme
• Kayıtlı noktayı UTM veya DDS’ye dönüştürme
• Kayıtlı noktaların tümünün koordinatlarını mail olarak gönderebilme
• Koordinatları manuel girme
• Haritadan nokta seçme
• Haritadan nokta seçerken adrese göre arama (geocoding)
• Haritadan seçilen noktanın adresini gösterme (reverse geocoding)
• GPS yardımıyla nokta seçme

İleride Eklenecek Özellikler:

• KorTrans kullanıcı adı ve şifresi ile noktaları cloud’a kaydetme, gönderme.
• Noktalardan poligon oluşturma, kaydetme.
• Poligon koordinatlarını ruhsat başvurusu için mail atma.
• Ruhsatların alanlarını görüntüleme.
• GPS yardımıyla fiziksel olarak ruhsat sahasında olup olmadığınızın tespiti.

Örnek Kullanım Videosu

Ondalık Dereceden UTM’ye Dönüşüm:

UTM’den Derece Dakika Saniyeye Dönüşüm:

Haritadan Seçilen Noktanın Dönüşümü:

Kayıtlı Noktaları Mail Atma:

Matematik ve polinomlar ile ilgili bu yazımızda karşılaşılan bir problemin analitik çözümüne kısaca değineceğiz.

Polinom kalan teoremine göre, P(x) polinomunun (x-a) binomuna bölümünden kalan, P(a)’dır. Diğer bir deyişle:

P(x) polinomunun (x-a) binomuna bölümünden kalan A, (x-b) binomuna bölümünden kalan B olsun.

Bizden istenen P(x) polinomunun, (x-a)(x-b) polinomuna bölümünden kalandır. Problemi kısaca ifade edelim:

Bildiklerimizi yerlerine koyalım:

Sonuç

Aşağıdakine benzer bir formülü tüm çabalarım neticesinde googleda bulamadım, belki de ne yazacağımı bilemediğimdendir…

Örnek

P(x) polinomunun (x+2) binomuna bölümünden kalan 3, (x-4) binomuna bölümünden kalan -9′dir. P(x)’in (x+2)(x-4) polinomuna bölümünden kalan nedir?

Verilenler:

Formülümüzde yerine koyalım:

NOT: Bu yazıdaki kod örnekleri kısaltılarak verilmiştir. Kod belgeleri için Doxygen ile yaratılmış olan mikrositeyi inceleyebilirsiniz (yazıdaki eklemeleri içerecek şekilde güncellenmiştir).

NOT: Her tür fikir, öneri ve eleştirinizi yorumlara yazabilirsiniz, teşekkür ederiz.

İçindekiler

• Gerekenler
• CCL Nedir?
• CCL için Önişleme
• CPU CCL Filtresi: CpuCCLFilter
• Filtre Örnekleri
• İndirmeler

Gerekenler

• VS 2010 ve C/C++ Bilgisi
• OpenCV ile görüntü yakalama aşinalığı. Windows için OpenCV 2.2′yi patchlemeyi unutmayın! Önceki yazımızı inceleyebilirsiniz.
• VS2010 ile CUDA projesi yaratabilmek. Önceki yazımızı inceleyebilirsiniz.
• CUDA içeren kodları çalıştırabilmek için CUDA destekli bir ekran kartı.
• Derleyici includeları, libraryleri ve hataları ile uğraşmak için bolca sabır.
• Önceki yazımızda detayları bulabilirsiniz: CUDA ile OpenCV kullanarak Webcam Görüntü İşleme

CCL Nedir?

Connected Components Labeling, görüntüde birleşik olan nesneleri etiketleyerek birbirinden ayırdedebilecek hale getiren algoritmaya verilen addır. Burada en önemli tanım, “görüntüde birleşik” tamlamasıdır. Bu filtredeki kodlar, wikipediadaki CCL açıklamasından yola çıkılarak yazılmıştır.

Görüntünün birleşik olması, komşu piksellerin renklerinin aynı veya belli bir derecede yakın olması ile ölçülür. Komşulukları gözönüne alırken 4-komşu ve 8-komşu modelleri kullanılabilir. 4-komşu modeli, ana yönler olan kuzey, güney, doğu ve batı komşularıdır. 8-komşu modelinde ara yönlerdeki komşular da hesaba katılır.

4-komşuluk

8-komşuluk

CCL için Önişleme

Renk Benzerliği

Renk benzerliği, CCL filtremizde birbiri ile aynı olarak nitelendirilecek renkleri ayırdetmemize yarar. Basit olarak gri skala uzayında uzaklığı 10′dan küçük olan renkler aynı sayıldı. Standart bir webcamin yakaladığı görüntülerde (en azından benimkinde) RGB noise denilen her renkten gürültü vardır. Webcam sabit bir yere bakarken ve görüntüde hiç hareket yokken bile yakalanan resmin pikselleri kısıtlı bir aralıkta sürekli değişir. Renklerin aynı olmasını katı bir şekilde gerektirmeyerek saptanan etiket sayısını düşürüyoruz, bir bakıma bu gürültüye bağışıklık kazanıyoruz.

Thresholding

Thresholding, belli bir aralığa sahip değeri, iki adet değere indirgemenin bir yoludur. Örneğin değerimiz 0 ile 255 arasında ise, threshold değerimiz 90 ise, 90′dan küçük değerler 0, büyük ve eşit değerler 1 grubuna denk gelir. CCL, threshold işlemi görmüş görüntü üzerinde çalışır. CCL algoritması için 0 arkaplan, 1 nesne demektir.

CPU CCL Filtresi: CpuCCLFilter

ISingleImageFilter arayüzünü kullanarak yazılan filtrede en önemli metod olan findConnectedComponents kısaca anlatılarak gösterilmiştir.

/**
	\ref ptKernelLauncher tipinde metod.

	\param width Görüntünün piksel olarak genişliği
	\param height Görüntünün piksel olarak yüksekliği
	\param rowStride Görüntünün hafızadaki byte olarak genişliği.
	\param imageData Görüntü verisi.
	\param outImageData Etiket görüntü verisi.
	\param outLabelBitmap Etiket integer bitmap.

	Görüntüdeki birleşmiş birimleri bulur. Connected Component Labeler.
*/
template<bool eightConnected>
void CpuCCLFilter::findConnectedComponents(int width, int height, int rowStride, char* imageData, char* outImageData, int* outLabelBitmap)
{
	// label bitmap	

	// disjoint set için tip ve map tanımları.
	typedef std::map<short, std::size_t> rank_t; // element order.
	typedef std::map<short, short> parent_t;

	rank_t rank_map;
	parent_t parent_map;

	boost::associative_property_map<rank_t>   rank_pmap( rank_map );
	boost::associative_property_map<parent_t> parent_pmap( parent_map );

	// disjoint sets yaratılır.
	boost::disjoint_sets<boost::associative_property_map<rank_t>, boost::associative_property_map<parent_t>>
		ds( rank_pmap, parent_pmap );

	boost::unordered_set<short> elements;

	short labelNumber = 0;

	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			outLabelBitmap[i*rowStride + j] = 0;
		}
	}

	// tüm pikseller gezilir
	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			// if pixel is not background.
			if( imageData[i*rowStride + j] != 0 )
			{
				if(j > 0 & i > 0 &
					isSameColor( imageData[i*rowStride + j - 1], imageData[(i - 1)*rowStride + j]) // same value
					& isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )
				)
				{
					// west ve north aynı
					ds.union_set( outLabelBitmap[i*rowStride + j - 1], outLabelBitmap[(i - 1)*rowStride + j] );
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[i*rowStride + j - 1];
				}

				if(j==0 & i > 0 & isSameColor( imageData[i*rowStride + j], imageData[(i - 1)*rowStride + j] ))
				{
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[(i-1)*rowStride + j];
				}

				// West pixel
				if(j > 0 & isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] ))
				{
					// west pixel ile aynı label.
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[i*rowStride + j - 1];
				}

				// west farklı north aynı.
				if(
					(j > 0 & !isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )) // west different value
					& (i > 0 & isSameColor( imageData[(i-1)*rowStride + j], imageData[i*rowStride + j] )) // north same value
				)
				{
					// north ile aynı
					outLabelBitmap[i*rowStride + j] = outLabelBitmap[(i-1)*rowStride + j];
				}

				// west ve north farklı
				if(   ((j > 0 &;amp;& !isSameColor( imageData[i*rowStride + j - 1], imageData[i*rowStride + j] )) || j == 0) // west different value
					& ((i > 0 & !isSameColor( imageData[(i-1)*rowStride + j], imageData[i*rowStride + j] )) || i == 0) // north different value
				)
				{
					labelNumber++;
					ds.make_set(labelNumber);
					elements.insert(labelNumber);
					outLabelBitmap[i*rowStride + j] = labelNumber;
				}

				// northeast ve northwest kontrol edilir. (çaprazlar).
				if(eightConnected)
				{
					// northwest
					if(j > 0 & i > 0
						& isSameColor( imageData[(i-1)*rowStride + j - 1], imageData[i*rowStride + j] )
					)
					{
						// northwest ile aynı
						ds.union_set( outLabelBitmap[(i-1)*rowStride + j - 1], outLabelBitmap[i*rowStride + j] );
					}

					// northeast
					if(j+1 < width & i > 0
						& isSameColor( imageData[(i-1)*rowStride + j + 1], imageData[i*rowStride + j] )
					)
					{
						// northeast ile aynı
						ds.union_set( outLabelBitmap[(i-1)*rowStride + j + 1], outLabelBitmap[i*rowStride + j] );
					}
				}
			}
		}
	}

	int cnt = ds.count_sets(elements.begin(), elements.end());

	printf("Component count: %i\n", cnt);

	// second pass - label output image and colorize.
	for(int i = 0; i < height; i++)
	{
		for(int j = 0; j < width; j++)
		{
			int labelNo = ds.find_set( outLabelBitmap[i*rowStride + j] ); // pikselin etiketi bulunur.
			int R =0, G=0, B=0;

			// etiketler renklendirilir.
			hsl_to_rgb( 1.0f * labelNo / labelNumber, .8f + .2f * labelNo / labelNumber, .75f, &R, &G, &B );

			int idx = i * rowStride + j;

			outImageData[idx * 3 + 0] = (char)(B);
			outImageData[idx * 3 + 1] = (char)(G);
			outImageData[idx * 3 + 2] = (char)(R);
		}
	}
}

Filtre Örnekleri

CpuCCLFilter:

İndirmeler

Dosyalar 7-zip ile sıkıştırılmıştır.

• Proje Kodları: ImageFilterLib – CCL – HelloOpenCV
• Doxygen Belgeleri Mikrositesi

Serbestçe kullanabileceğiniz bir silverlight uygulaması olan KorTrans SL v1.0′a bu linkten erişebilirsiniz.

• Tüm Türkiye’deki paftaları, haritadan nokta seçerek bulabilirsiniz.
• UTM, Derece-Dakika-Saniye ve Ondalıklı Derece sistemleri arasında dönüşüm yapabilirsiniz.
• Pafta ismini “İSTANBUL-F22-b3″ veya “F22-b3″ şeklinde girerek de paftayı bulabilirsiniz.
• Seçilen pafta üzerinde UTM grid çizgilerini gösterebilirsiniz.
• Ölçeğinize göre belirlenen komşu paftaları görebilirsiniz.Her zamanki gibi değerli yorumlarınızı bekliyoruz.

Program silverlight ile çalışır. Silverlight, Microsoft’un bir platformudur, yüklemek çok kolaydır.

Kullanım

Programda markeri sürükleyerek koordinatı belirlersiniz.

Not: Sol üst köşedeki dönüşüm fonksiyonlarını denemeyi unutmayın!

Linkler

KorTrans SL: http://www.dissipatedheat.com/kortrans.

Biraz uzun soluklu olan bu yazımıza OpenCV ve CUDA hakkında kısa maddeler ile başlayalım.

NOT: Bu yazıdaki kod örnekleri kısaltılarak verilmiştir. Kod belgeleri için Doxygen ile yaratılmış olan mikrositeyi inceleyebilirsiniz.

NOT: Her tür eleştirinizi yorumlara yazabilirsiniz, teşekkür ederiz.

İçindekiler

• Gerekenler
• Görüntü İşleme ve Webcam
• ISingleImageFilter Kullanımı
• En basit filtre: IdentityFilter
• CPU Üzerinde Negatif Görüntü Filtresi
• Yeniden Hoşgeldin CUDA!
• Görüntü Negatifi – CUDA
• Texturelar
• Görüntü Negatifi – CUDA Texture
• Filtre Zinciri: SingleImageFilterChain
• UML Şeması
• Filtre Örnekleri

Gerekenler

• VS 2010 ve C/C++ Bilgisi
• OpenCV ile görüntü yakalama aşinalığı. Windows için OpenCV 2.2′yi patchlemeyi unutmayın! Önceki yazımızı inceleyebilirsiniz.
• VS2010 ile CUDA projesi yaratabilmek. Önceki yazımızı inceleyebilirsiniz.
• CUDA içeren kodları çalıştırabilmek için CUDA destekli bir ekran kartı.
• Derleyici includeları, libraryleri ve hataları ile uğraşmak için bolca sabır.

OpenCV Nedir?

OpenCV, açık kaynaklı bir bilgisayarlı görselleştirme kütüphanesidir. Amacı görüntü işleme ve görselleştirmede sık kullanılan metodların kolaylıkla erişilebilir olmasını sağlamaktadır.

CUDA Nedir?

CUDA, Compute-Unified Device Architecture, hesaplamaların grafik işlemcisi üzerinde gerçekleştirilmesi amacıyla CPU’dan zaman bağımsız olarak ve yüzlerce çekirdek üzerinde binlerce thread kullanarak paralel hesaplamaya olanak veren nVidia’nın bir kaç senedir satışa sunulan ekran kartlarında uyguladığı bir mimaridir. Bu muazzam paralellik(massively parallel) bize doğru kullanıldığında hesaplamada hız olarak dönecektir.

Görüntü İşleme ve Webcam

Görüntü işleme, görüntüye uygulanan matematiksel bir işlemi ifade eder. Örneğin görüntünün negatifinin alınması, görüntünün 90 derece çevrilmesi, görüntünün bir kurala göre bulandırılması vb. basit görüntü işleme metodlarıdır. Bir önceki yazımızda bahsettiğimiz OpenCV ile webcam görüntüsü yakalamayı bu yazımızda bir adım ileri götürerek görüntü işleme ile genelleştirilmiş olarak birleştireceğiz.

Görüntünün webcam üzerinden, bir avi dosyasından veya başka bir kaynaktan geliyor olması OpenCV kullandığımız için fark etmemektedir.

Özetle OpenCV Görüntü Yakalama

1. OpenCV ile kamerayı açıyoruz.
2. İlk kareyi yakalıyoruz.
3. İlk kareyi hatasız yakaladıysak devam ediyoruz.
4. Kullanıcının ‘q’ tuşuna basması ile çıkacağı bir döngüye giriyoruz.
   1. Kareyi yakalıyoruz.
   2. Kareyi istediğimiz boyuta getiriyoruz.(Örnekte 640 x 480)
   3. Görüntü işleme metodumuzu çağırıyoruz.
   4. Kareyi ekranda gösteriyoruz.
5. Programdan çıkıyoruz.

Arayüzler, Sınıflar, Kalıtım ve dahası

Burada geliştireceğimiz nokta, görüntü işlemenin main.cpp içerisindeki bir global metod olmaktan çıkarılmasıdır. Görüntü işleme için kullanabileceğimiz en basit arayüzü düşündüğümüzde, bu arayüzde görüntünün boyutları ve Filtrele metodundan başka bir içeriğe ihtiyaç olmadığını görüyoruz.

Bellek ile ilgili ayırma ve serbest bırakma özelliğinin de görüntü işleme sınıfında olması için InitFilter ve ReleaseFilter metodları kullanılmıştır.

Bu basit arabirimi aşağıdaki UML şemasında inceleyebiliriz.

main.cpp dosyasında ISingleImageFilter Kullanımı

• Filtreyi yaratmak,
• InitFilter’ı looptan önce çağırmak,
• ReleaseFilter’ı looptan çıkınca çağırmaktır.

// ... OpenCV kamera açılır, kare yakalanır.

// Kullanacağımız filtre yaratılır.
ISingleImageFilter* myFilter = new IdentityFilter();

// Filtreye görüntünün boyutu bildirilir.
myFilter->InitFilter( 640, 480 );

// OpenCV görüntü yakalama döngüsü.
while( key != 'q' )
{
//	... kare yakalama.

	// Yakalanan görüntü işlenir.
	myFilter->FilterImage( imageData );

//	... kare gösterim.
}

// Filtre kaynaklarının serbest bırakılması istenir.
myFilter->ReleaseFilter();

// ... program çıkışı.

ISingleImageFilter Kullanımı

ISingleImageFilter‘da tüm filtrelerin kullanacağı en az iki değişken vardır. Görüntünün genişliği ve yüksekliği. Bu değişkenleri üye değişkenlerinde tutan ve tüm filtrelere ortak özellik eklenmesi gerektiğinde geliştirilebilecek bir sınıf olarak SingleImageFilter sınıfı yazılmıştır.

SingleImageFilter, ISingleImageFilter sınıfından kalıtlanmıştır ve InitFilter metodu aşağıda verilmiştir.

	virtual void InitFilter(int width, int height)
	{
		this->width = width;
		this->height = height;
		this->isInited = true;
	}

En basit filtre: IdentityFilter

ISingleImageFilter arayüzünün kullanımını en basit şekliyle göstermek amacıyla yazılmış bir filtre sınıfıdır. Kalıtladığı SingleImageFilter sınıfının FilterImage metodunu override eder.

class IdentityFilter : public SingleImageFilter
{
public:
	IdentityFilter()
	{
	}

	/** Görüntüde değişiklik yapmadan çıkar. */
	virtual void FilterImage(char* imageData)
	{
		return; // imajı değiştirmeden dön.
	}
};

CPU Üzerinde Negatif Görüntü Filtresi

CPU üzerinde çalışan filtrelere örnek olarak negatif görüntü filtresi verilmiştir. Bu sınıfın sadece FilterImage metodu aşağıdadır.

	/** Görüntünün RGB kanallarının tersini alır. */
	virtual void FilterImage(char* imageData)
	{
		for(int i=0; i<3*width*height; i++)
		{
			*( imageData + i ) = ( unsigned char ) ( 255 - *( imageData + i ) ); // her pikselin her kanalının negatifini al.
		}
	}

Buraya kadarki filtrelerin UML şemasını gözden geçirecek olursak:

Yeniden Hoşgeldin CUDA!

CUDA kodlarının çalışabilmesi için CUDA SDK 3.2 yazılımının bilgisayarınızda yüklü olması gerekmektedir. Kurulum için: VS2010 ile CUDA 3.2 Projesi Yaratmak

Görüntü işleme, CUDA kullanarak paralelleştirilmeye çok yatkın bir alandır. Her ne kadar bu yazıda anlatılan görüntü işleme metodları muazzam bir işlem gücü gerektirmese de metodların GPU’da CPU’dan daha hızlı çalıştığını farkedebilirsiniz.

CUDA üzerinde OpenCV’de yakaladığımız görüntüyü işleyebilmek için öncelikle bu görüntünün verisini ekran kartının belleğine yüklemeliyiz. Hesaplamayı GPU üzerinde yaptıktan sonra sonucu da CPU belleğine geri almalıyız.

SingleCudaFilter::FilterImage metodu

• Kareyi yakala
• SingleCudaFilter::FilterImage
  • Kareyi ekran kartı belleğine yükle
  • Filtreyi GPU üzerinde uygula
  • Sonucu CPU belleğine geri al
• Sonraki kareye geç

Ekran kartı belleğinin ayrılması InitFilter metodunda, serbest bırakılması ReleaseFilter metodunda, verilerin ekran kartına kopyalanması ise FilterImage metodunda yapılır.

CUDA kullanmak için bir de kernele ihtiyacımız var. SingleCudaFilter sınıfında bu kernel parametrik olarak constructorda alınmaktadır. CUDA kernellerini derlemek için nvcc adlı nVidia derleyici sürücüsünün çalışması gerekmektedir ve bu kernellere olan referanslar MSVC derleyicisi tarafından algılanmamaktadır, dolayısıyla kernellerin metod işaretçilerini doğrudan kullanamıyoruz.

Kernelleri çağırmak için gereken griddeki blok ve bloktaki thread sayısını kullanarak kerneli çağıran metodlara proje kapsamında “kernel launcher” adı verilmiştir. Kernel launcherlar, aynı zamanda ptKernelLauncher tipindeki metod işaretçisi imzasını taşırlar.

/**
	Yaratıcıda alınan kerneli çağırır.

	\param imageData Görüntünün BGR kanal sıralı bellekteki adresi.

	Görüntüyü normalize ederek kernelLauncher işaretçisinin gösterdiği metodu çağırır ardından görüntüyü denormalize eder( [0, 255] aralığına ).
	Kernelde işlenen görüntüden sonuç olarak [0, 1] aralığı dışında bir değer dönerse o kanalın değeri [0, 255] aralığından dışarıda olabilir. Bu durumda değer yakın olduğu sınıra indirgenir.
*/
virtual void FilterImage(char* imageData)
{
	// imageData değişkenindeki görüntü verisi normalize edilerek h_Image değişkenine aktarılır.
	for(int i=0; i<3*width*height; i++)
	{
		*(h_Image + i) = (unsigned char)*(imageData + i) / 255.0f; // normalize and copy image
	}

	/*
		Görüntü GPU belleğine kopyalanır.
	*/

	cudaMemcpy( d_Image, h_Image, 3 * sizeof(float) * width * height, cudaMemcpyHostToDevice );
	checkCUDAError("FilterImage: memcpy");

	/*
		Constructorda verilen kernel çalıştırılır.
	*/
	kernelLauncher( d_Image, width, height );

	/*
		Sonuçlar CPU belleğine kopyalanır.
	*/
	cudaMemcpy( h_Image, d_Image, 3 * sizeof(float) * width * height, cudaMemcpyDeviceToHost);
	checkCUDAError("FilterImage: memcpy2");

	/*
		h_Image değişkenindeki normalize edilmiş görüntü verisi [0, 255] aralığına çekilir.
	*/
	for(int i=0; i<3*width*height; i++)
	{
		*(imageData + i) = satchar(*(h_Image + i) * 255);
	}
}

Projedeki kernelleri çağırmak için kullanılan metod işaretçisi ve kullanımı:

typedef void (*ptKernelLauncher)(float*, int, int);

ptKernelLauncher kernelLauncher; // kernelLauncher değişkeni tanımlanır.

kernelLauncher = deviceInvertLaunch; // deviceInvertLaunch metodunun işaretçisi tanımlanan değişkene atanır.

kernelLauncher( d_Image, width, height ); // metod, işaretçisi üzerinden çağrılır. Çağrılan metod, GPU üzerinde çalışacak olan kerneli configuration parametreleri ile çağırır.

Kerneli parametreleri ile çağırmak:

    dim3 dimBlock( BLOCK_SIZE, BLOCK_SIZE );
    dim3 dimGrid( height / dimBlock.x, width / dimBlock.y );

    gpuInvert<<< dimGrid, dimBlock >>>( d_Image, width, height);

Görüntü Negatifi – CUDA

CUDA kerneli kullanarak görüntünün negatifini almak için kernelimizde görüntünün her bir pikselinin tersini almalıyız. Bu işlem için kernel aşağıdaki gibidir.

/**
	Görüntünün tersini alan kernel.

	\param image [0, 1] aralığına normalize edilmiş, BGR kanal sıralı görüntünün GPU belleğindeki adresi.
	\param width Görüntünün piksel olarak genişliği
	\param height Görüntünün piksel olarak yüksekliği

	Metod GPU üzerinde çalışır, çıktısını image parametresinin üzerine yazar.

	*/
__global__
void gpuInvert(
	float* image,
	int width,
	int height
	)
{
	int row = blockIdx.y * BLOCK_SIZE + threadIdx.y;
	int col = blockIdx.x * BLOCK_SIZE + threadIdx.x;

	int cIdx = ( row * width + col ) * 3; // 3 ile çarpım RGB için, linearIndex.

	// normalize edilmiş pikselleri 1'den çıkarttığımızda görüntünün negatifini almış oluruz.
	*( image + cIdx     ) = 1 - *( image + cIdx     ); // Blue kanalı
	*( image + cIdx + 1 ) = 1 - *( image + cIdx + 1 ); // Green kanalı
	*( image + cIdx + 2 ) = 1 - *( image + cIdx + 2 ); // Red kanalı
}

Bu kernelin kullanımı iki şekildedir. Birincisi SingleCudaFilter sınıfını doğrudan main.cpp içinde kullanarak:

// deviceInvertLaunch kernel launcher metodu SingleCudaFilter sınıfına parametre olarak verilir.
ISingleImageFilter* myFilter = new SingleCudaFilter(deviceInvertLaunch);

İkincisi ise bu parametreyi kendi constructorında SingleCudaFilter sınıfının constructoruna veren bir sınıf yazmaktır. Tek bir filtre için tek bir sınıf yazmanın getirisi, hangi kernelin kullanılacağını bilmeye gerek olmamasıdır, ptKernelLauncher, sınıfın içinde bir kere yazılır.

/**
	CUDA kullanarak GPU üzerinde görüntünün negatifini alan filtre sınıfı.
*/
class CudaInvertFilter : public SingleCudaFilter
{
public:
	/**
		\ref deviceInvertLaunch metod işaretçisi parametresi ile SingleCudaFilter yaratıcısını çağırır.
	*/
	CudaInvertFilter()
		: SingleCudaFilter(deviceInvertLaunch)
	{
	}
};

Texturelar

Buraya kadar bahsedilen CUDA filtreleri, tamamen ekran kartı global belleği üzerinden çalışmaktadır. Okumalar texture belleğinden yapılarak zaman kazanılabilir ve texture önbelleğinden otomatik olarak faydalanılabilir. Texture önbelleği, erişimde yerellik olduğu zaman örneğin bir piksele eriştiğinizden hemen ardından o pikselin 2 boyutlu düzlemdeki komşularına eriştiğinizde devreye girerek bellek okuma işlemlerinin bir miktar hızlanmasını sağlayabilir.

Textureları CUDA ile kullanabilmek için cuArray tipinde tanımlanan değişken üzerinden işlemler yürütülür. Texture üzerine hiçbir zaman doğrudan veri kopyalanmaz çünkü texturelar salt-okunurdur. Bir CUDA textureına cuArray atanarak yazma işlemleri cuArray‘e yapıldığında, texture otomatik olarak yazılan veriyi üzerine alacaktır.

Texturelar ile ilgili karşılaşılan sorun, kullanılacak textureın, kernelin bulunduğu .cu dosyasında olması zorunluluğudur. Ortak bir başlık dosyasında texture tanımlanıp hem kernelin bulunduğu dosyadan, hem de bu textureı yönetmek istediğimiz sınıfın dosyasından içerildiğinde, texturelar nvcc tarafından farklı olarak algılanmaktadır.

Texture değişkeninin scopeu:

Kernelin bulunduğu dosya dışındaki bir sınıftan texturea veri yüklemesi ve diğer texture ayarlarının yapılması için nVidia’nın CUDA Driver API’si kullanılabilir. Adı sizi korkutmasın, tek satırda yapılan işlemi başka bir dosyadan yapmak istediğimizde bir kaç satırda yapıyoruz, tek fark bu.

SingleCudaTexFilter sınıfında texture yönetimi ile ilgili bir diğer ince nokta da CUDA kodlarında cudaGetTextureReference ve benzeri metodların parametre olarak const bir referans beklemesidir. Bizim niyetimiz textureı değiştirmek olduğundan CUDA Driver API’si ile anlaşabilmek için ara bir değişken kullanıyoruz.

cuda_runtime_api.h içinde cudaGetTextureReference tanımı:

extern __host__ cudaError_t CUDARTAPI cudaGetTextureReference(const struct textureReference **texref, const char *symbol);

SingleCudaTexFilter içerisinde textureın const‘unun kaldırılarak ara değişkene atanması ve kullanımı:

	const textureReference* constTexRefPtr;
	textureReference* texRefPtr;

	...

	// cudaGetTextureReference, istediği gibi const texture referansı ile çağrılır.
	cudaGetTextureReference(&constTexRefPtr, textureSymbolName);
	checkCUDAError("get texture reference");

	// const olan referans, const olmayan referansa dönüştürülerek saklanır.
	texRefPtr = const_cast<textureReference*>( constTexRefPtr );
	channelDesc = cudaCreateChannelDesc<float4>();

	// const olmayan texture referansının kullanımı.
	cudaMallocArray( &cu_array, &texRefPtr->channelDesc, width, height );
	checkCUDAError("malloc device image");

	...

	// cu_array üzerine kopyalanan veriler texture atanacak.
	cudaMemcpyToArray( cu_array, 0, 0, h_Image, sizeof(float4) * width * height, cudaMemcpyHostToDevice);
	checkCUDAError("FilterImage: memcpy");

	// cu_array, texturea atanır.
	cudaBindTextureToArray( texRefPtr, cu_array, &texRefPtr->channelDesc );

Texture kullanımı ile ilgili olarak SingleCudaTexFilter.cu ve SingleCudaTexFilter.h dosyalarını inceleyebilirsiniz.

Görüntü Negatifi – CUDA Texture

CUDA ile texture belleğini kullanarak görüntünün negatifini almak için kernelimizde görüntünün her bir pikselini textureın her bir pikselinin tersinden oluşturmalıyız. Bu işlem için kernel aşağıdaki gibidir.

/**
	Texture kullanarak görüntünün negatifini alan kernel.

	\param image [0, 1] aralığına normalize edilmiş, BGR kanal sıralı görüntünün GPU belleğindeki adresi.
	\param width Görüntünün piksel olarak genişliği
	\param height Görüntünün piksel olarak yüksekliği

	Metod GPU üzerinde çalışır, çıktısını image parametresinin üzerine yazar.
*/
__global__
void gpuTexInvert(
	float* image,
	int width,
	int height
	)
{
	int row = blockIdx.y * BLOCK_SIZE + threadIdx.y;
	int col = blockIdx.x * BLOCK_SIZE + threadIdx.x;

	int cIdx = ( row * width + col ) * 3; // 3 ile çarpım RGB için, linearIndex.

	// threade ait kordinatın texture uzayındaki kordinatı bulunur.
	float tu = (float)col / width;
	float tv = (float)row / height;

	// Texture üzerinden görüntü verisi okunur.
	float4 texVal = tex2D( texInvert1, tu, tv );

	// Texture değerleri 1'den çıkartılarak global belleğe yazılır.
	*( image + cIdx )     = 1 - texVal.x;
	*( image + cIdx + 1 ) = 1 - texVal.y;
	*( image + cIdx + 2 ) = 1 - texVal.z;
}

Texture kullanan kernel de texture kullanmayan CUDA negatif kerneli gibi iki şekilde kullanılabilir. Detaylar için kaynak kodu inceleyebilirsiniz.

Filtre Zinciri: SingleImageFilterChain

Filtre zinciri, birbiri ardına uygulanacak filtreleri barındıran bir sınıftır. Bu sınıf SingleImageFilter sınıfından kalıtlanmıştır. AppendFilter metodu ile sınıfa işlemesi için filtreleri sıralı olarak verebilirsiniz. FilterImage metodu çağrıldığında zincirdeki tüm filtreler için FilterImage metodu çağrılacaktır.

ISingleImageFilter* myFilter1 = new SingleCudaTexFilter(deviceTexAbsDiffLaunch, "texAbsDiff1");
ISingleImageFilter* myFilter2 = new CpuInvertFilter();

SingleImageFilterChain* myFilter = new SingleImageFilterChain();
myFilter->AppendFilter( myFilter1 );
myFilter->AppendFilter( myFilter2 );

// myFilter'a atanmış olan filtre zinciri, ISingleImageFilter arayüzünü gerçeklediği için diğer filtreler gibi kullanılabilir.

UML Şeması

UML Şeması basitleştirilmiş olarak verilmiştir:

Filtre Örnekleri

IdentityFilter:

CudaSepiaFilter:

CudaTexBoxBlurFilter:

SingleImageFilterChain: deviceTexAbsDiffLaunch kerneli ardından CpuInvertFilter:

İndirmeler

Dosyalar 7-zip ile sıkıştırılmıştır.

• Proje Kodları: ImageFilterLib – HelloOpenCV
• Doxygen Belgeleri Mikrositesi

NOT: Kerneller optimize edilmemiştir.

OpenCV, açık kaynaklı bir bilgisayarlı görselleştirme kütüphanesidir. Amacı görüntü işleme ve görselleştirmede sık kullanılan metodların kolaylıkla erişilebilir olmasını sağlamaktadır. Yazımızda kullandığımız OpenCV 2.2 ile webcam görüntüsü işlerken bu kolaylığı farkedeceğiz.

Webcam görüntüsünü alacağım derseniz bir yolu da DirectShow kullanmaktır ki bu yol uzun ince bir yoldur, bkz. DirectShow Webcam

Webcam Görüntüsünü Almak

Yüklü ve windows tarafından tanınmış olan webcaminizden OpenCV kullanarak görüntü almak için yazmanız gereken kod sadece tek bir satırdır.

	CvCapture* capture = 0;
	capture = cvCaptureFromCAM(0);
	IplImage* videoFrame = NULL;

	videoFrame = cvQueryFrame(capture); // kameradan görüntü alınır

Gerekenler

• VS 2010 ve C/C++ Bilgisi
• OpenCV 2.2 Kurulumu
• OpenCV’yi kendiniz patchlemek isterseniz:
  • CMake, OpenCV’yi patchledikten sonra build etmek için.
  • OpenCV 2.2 Windows webcam patchi: İngilizce
• Patchli dll ve libleri indirmek isterseniz:
  • İndirmeler

İzlenen Yol

OpenCV 2.2 Patch

OpenCV 2.2 sürümünde mevcut olan bir bug, windows makinalarda görüntü alınmasına engel olmaktadır. Bu bugın varlığını keşfedinceye kadar bilgisayarımdan ve kameramdan şüphe etmiştim, neyseki şüphelerim yersizmiş. Patch deyince gözünüz korkmasın, sadece tek bir dosyada iki satır değişiklik yapmak gerekiyor. Bu satırlar için bkz. OpenCV 2.2 patch.

Yok ben dosyalarımı patchli kullanırım derseniz İndirmeler bölümünden OpenCV patch dosyasını indirip içindeki dll dosyalarını c:\opencv2.2\bin içerisinde, lib dosyalarını da c.\opencv2.2\lib dizinine oradaki dosyaların üzerine yazarak kopyalayabilirsiniz.

Visual Studio Projesi

• Empty Win32 Console Project yaratarak yolculuğumuza başlıyoruz.
• Projemizin özellik sayfasında VC++ Directories’de includeları ekliyoruz:

  C:\OpenCV2.2\include

• Projemizin özellik sayfasında VC++ Directories’de libraryleri ekliyoruz:

  C:\OpenCV2.2\lib

• Kullanacağımız kütüphane dosyalarını Linker->Input->Additional Dependencies’e ekliyoruz.

  opencv_core220.lib
  opencv_highgui220.lib
  opencv_imgproc220.lib

• Yaratacağımız main.h dosyasına içeriği ekliyoruz:

  #pragma once // Header dosyasına birden fazla referans olsa bile sadece 1 kere işlensin.
  
  #include <stdio.h>
  #include <stdlib.h>
  
  #include "opencv2\opencv.hpp"
  
  

• Yaratacağımız main.cpp dosyasına webcamden capture edip görüntüyü negatif yaparak ekranda göstermeye yarayacak aşağıdaki kodu ekliyoruz.

  
  #include "main.h" // tüm başlıklarımızı ve tanımlamalarımızı içeren başlık dosyası.
  
  int main( int argc, char** argv )
  {
  	int key = -1;
  
  	CvCapture* capture = 0;
  
  	// İlk tanımlı kameranın tutacağını al. (tutacak = handle).
  	capture = cvCaptureFromCAM( 0 );
  	if( !capture )
  	{
  		// Tutacak geçersiz ise programdan çık.
  		fprintf( stderr, "Kamera tutacağı edinilemedi...\n" ); // bilgilendiiir.
  		exit( EXIT_FAILURE );
  	}
  
  	// Görüntü için pointer.
  	IplImage* videoFrame = NULL; 
  
  	// ilk kareyi yakala.
  	videoFrame = cvQueryFrame( capture ); 
  
  	if( !videoFrame )
  	{
  		// Kare yakalanamadı, programdan çık.
  		printf( "Kare yakalanamadı...\n" );
  		exit( EXIT_FAILURE );
  	}
  
  	// MainVideo adında bir gösterim penceresi yarat.
  	cvNamedWindow( "MainVideo", 1 );
  
  	// q tuşuna basana kadar dön.
  	while( key != 'q' )
  	{
  		// Bir kare al.
  		videoFrame = cvQueryFrame( capture );
  
  		// Kare geçersiz ise loop biter.
  		if( !videoFrame )
  			break;
  
  		// Karenin tüm pixellerini ters çevir, negatif resim efekti.
  		// Not: Görüntü tipinin BGR olduğu varsayılmıştır. Normalde kontrol edilmelidir.
  		for( int i=0; i < videoFrame->imageSize; i++ )
  		{
  			videoFrame->imageData[i] = 255 - videoFrame->imageData[i];
  		}
  
  		// Negatif görüntüyü pencerede göster.
  		cvShowImage( "MainVideo", videoFrame );
  
  		key = cvWaitKey( 10 ); // 10ms tuş için bekle.
  	}
  
  	cvDestroyAllWindows(); // yarattığımız pencereyi yokeder.
  
  	cvReleaseCapture( &amp;amp;amp;amp;amp;amp;amp;capture ); // Kameranın tutacağını bırakır.
  
  	exit( EXIT_SUCCESS );
  }
  
  

Gerçek Zamanlı Webcam Negatifi

İndirmeler

Dosyaları açabilmek için farklı kaydederek uzantısını 7z yapınız.
Patchlenmiş OpenCV dosyaları: OpenCV2.2 webcam patch
Örnek Proje Kaynakları: HelloOpenCV

matMul1 (n adet global store):

d_C[ cIdx ] = 0;

// C matrisinin her bir hücresi için
for(int j=0; j<n; j++)
{
	// her bir eleman için C matrisinin bir elemanı okunur ve yazılır.
	d_C[ cIdx ] += *loc( d_A, n, i, j ) * *loc( d_B, r, j, k ); // global hafızaya yazılır(d_C).
}

matMul2 (1 adet global store):

float val = 0; // ara toplam değişkeni

// C matrisinin her bir hücresi için
for(int j=0; j<n; j++)
{
	val += *loc( d_A, n, i, j ) * *loc( d_B, r, j, k ); // local registera(val) yazılır.
}

// C matrisine bir kere yazılır.
d_C[ cIdx ] = val;

Paylaşık Hafıza (Shared Memory)

Paylaşılmış olmayan hafıza mı vardır dediğinizi duyar gibiyim. Global Hafıza da paylaşılmıştır elbet, herkes yazabilir herkes okuyabilir. Fakat burada bir nVidia terimi olarak geçen “paylaşık hafıza” bir blok içerisindeki threadler arasında paylaşılmıştır. Yani ancak aynı blok içerisindeki threadler aynı yeri okuyabilir ve aynı yere yazabilir.

Bir bloktaki threadler paylaşık hafızaya yardımlaşarak yükledikleri verileri kullanabilirler.

...

Ais[threadIdx.y][threadIdx.x] = *loc( d_A, n, i, j ); // A(i,j) elemanı Ais paylaşık hafızasına yüklenir.
Bis[threadIdx.y][threadIdx.x] = *loc( d_A, n, j, k ); // A(j,k) elemanı Bis paylaşık hafızasına yüklenir.

// kullanılacak elemanlar paylaşık hafızaya yüklenir.
__syncthreads(); // syncthreads, bloktaki tüm threadlerin bu noktaya erişmesini bekletir.

for(int k=0; k<BLOCK_SIZE;k++)
{
	val += Ais[threadIdx.y][k] * Bis[k][threadIdx.x];
}

// tüm threadlerin sonucu yazması beklenir.
__syncthreads(); // syncthreads, bloktaki tüm threadlerin bu noktaya erişmesini bekletir.

2. Optimizasyon (Paylaşık Hafıza)

Yapılan optimizasyonda paylaşık hafıza kullanılarak global hafızadan okuma sayısı düşürülmüştür.

__global__
void matMul3(
	float* d_C,
	float* d_A,
	float* d_B,
	int m,
	int n,
	int r)
{

	__shared__ float Ais[BLOCK_SIZE][BLOCK_SIZE];
	__shared__ float Bis[BLOCK_SIZE][BLOCK_SIZE];

	int i = blockIdx.x * BLOCK_SIZE + threadIdx.x;
	int k = blockIdx.y * BLOCK_SIZE + threadIdx.y;

	int cIdx = i*m + k;

	float val = 0; // ara toplam değişkeni

	for(int j=0; j < n / BLOCK_SIZE; j++)
	{
		Ais[threadIdx.y][threadIdx.x] = *loc( d_A, n, i, j );
		Bis[threadIdx.y][threadIdx.x] = *loc( d_B, n, j, k );

		// kullanılacak elemanlar paylaşık hafızaya yüklenir.
		__syncthreads();

		for(int k=0; k<BLOCK_SIZE;k++)
		{
			val += Ais[threadIdx.y][k] * Bis[k][threadIdx.x];
		}

		// tüm threadlerin sonucu yazması beklenir.
		__syncthreads();
	}

	// C matrisine bir kere yazılır.
	d_C[ cIdx ] = val;
}

Zamanlama

512 x 512 boyutlarında iki matrisin çarpım sürelerini karşılaştırabiliriz.

Referanslar

• Programming Massively Parallel Processors

Proje dosyasını açabilmek için farklı kaydederek uzantısını 7z yapınız.
Kaynakları indir: CUDA matris carpimi 2

A matrisinin i. satırının j. sütunundaki eleman


Bu yazımızdaki örnekler:

• C ile yazılmış naif matris çarpımı
• Optimize edilmemiş GPU kerneli
• 1. Optimizasyon

Naif CPU Matris Çarpımı

inline
float* h_loc(float* h_B, int width, int i, int j)
{
	return h_B + i*width + j;
}

void hostMatrixMultiply(
	float* h_C,
	float* h_A,
	float* h_B,
	int m,
	int n,
	int r)
{

	clock_t start = clock(), diff;

	for(int i=0; i<m; i++)
	{
		for(int k=0; k<r; k++)
		{
			float sum = 0;
			for(int j=0; j<n; j++)
			{
				sum += *h_loc(h_A, n, i, j) * *h_loc(h_B, r, j, k);
			}

			*h_loc(h_C, r, i, k) = sum;
		}
	}

	diff = clock() - start;

	int msec = diff * 1000 / CLOCKS_PER_SEC;
	printf("hostMatrixMultiply: %i ms\n", msec);

}

Optimize Edilmemiş GPU Kerneli

matMul1<<< dimGrid, dimBlock >>>( d_C, d_A, d_B, m, n, r);

__global__
void matMul1(
	float* d_C,
	float* d_A,
	float* d_B,
	int m,
	int n,
	int r)
{
	int i = blockIdx.x * BLOCK_SIZE + threadIdx.x; // GPU threadinin hesaplayacağı C matrisinin satırı.
	int k = blockIdx.y * BLOCK_SIZE + threadIdx.y; // GPU threadinin hesaplayacağı C matrisinin sütunu

	int cIdx = i*m + k; // Hesaplanacak elemanın C indisi.

	d_C[ cIdx ] = 0;

	// C matrisinin her bir hücresi için
	for(int j=0; j<n; j++)
	{
		// her bir eleman için C matrisinin bir elemanı okunur ve yazılır.
		d_C[ cIdx ] += *loc( d_A, n, i, j ) * *loc( d_B, r, j, k );
	}
}

1. Optimizasyon (Hafıza Erişimi)

__global__
void matMul2(
	float* d_C,
	float* d_A,
	float* d_B,
	int m,
	int n,
	int r)
{
	int i = blockIdx.x * BLOCK_SIZE + threadIdx.x;
	int k = blockIdx.y * BLOCK_SIZE + threadIdx.y;

	int cIdx = i*m + k;

	float val = 0; // ara toplam değişkeni

	// C matrisinin her bir hücresi için
	for(int j=0; j<n; j++)
	{
		val += *loc( d_A, n, i, j ) * *loc( d_B, r, j, k );
	}

	// C matrisine bir kere yazılır.
	d_C[ cIdx ] = val;
}

Zamanlama

Yapılan bu ufak değişiklikle kazanılan 128 x 128 boyutlarında iki matrisin çarpım sürelerini karşılaştırabiliriz.

Proje dosyasını açabilmek için farklı kaydederek uzantısını 7z yapınız.
Kaynakları indir: CUDA matris carpimi 1

For English: CUDA 3.2 on VS2010 in 9 steps

Bu kısa yazımızda CUDA ile programlamaya giriş yapmanın zevkini yaşayacağız. CUDA ile ekran kartındaki GPU üzerinde çalışacak programlar yazabilirsiniz. Bu programlar GPU’daki özel hardware threadler üzerinde paralel olarak çalışırlar. Detaylı bilgi için tıklayınız.

4. adımdaki dosyalar yok ise indiriniz: CUDA 3.2 Build Rules

Aşağıdaki adımları izlemek için gerekenler:

• Visual Studio 2008 kurulumu
• Visual Studio 2010 kurulumu
• nVidia CUDA 3.2 SDK kurulumu
• Genel Visual Studio menüleri ve kullanımı

9 Adımda CUDA Derleme

1. Yeni bir Win32 Console Application yaratın.



2. Projeyi yaratırken empty project seçeneğini işaretleyin. Boş bir projeye kaynak dosyasını kendimiz ekleyeceğiz.



3. cu uzantılı kaynak dosyası ekleyin. Bu dosya nvidianın compiler driverı olan nvcc.exe dosyası tarafından işlenerek vs2008 ile gelen versiyon 9 C derleyicisine gönderilecektir.



4. CUDA 3.2 SDK’nın kuruluşuile gelen Build Customizationların yerinde olduğu kontrol edilir.



5. Platform Toolset v90 olarak değiştirilir. Visual Studio 2010, CUDA dosyalarını derlemeyi destekler fakat altyapı olarak bir önceki versiyon C derleyicisini kullanır. Dolayısıyla Visual Studio 2008′in makinada kurulu olmasına ihtiyaç vardır.



6. Eklediğimiz CU dosyasının özelliklerinden Item Type olarak CUDA C/C++ seçilir.



7. Project Build Customizations olarak CUDA 3.2 seçilir. Bende CUDA 3.1 SDK’sı da yüklü olduğu için o da seçilebiliyor.



8. CUDA’nın kullandığı kütüphaneler eklenir( cuda.lib ve cudart.lib ).



9. Yaratılan CU dosyasından CUDA fonksiyonlarının çağrılabildiği ve derlenebildiği görülür.