Algoritmus na 4-bodovou kalibraci 2D mapy?

[RayeR]

Zdar,
neresil tu nekdo nahodou problem kalibrace 2D mapy?
Potreboval bych napsat fci, ktere dam 4 2D souradnice bodu na mape (v pixelech) a 4 2D souradnice (v nejakem systemu, treba wgs), a nasledne mi tato fce podle zadaneho bodu [x,y] vrati prepoctene souradnice [x',y']v pixelech (a naopak, inverzni fce).
Mam napsanou jednochou verzi pro 2-bodovou kalibraci, ktera ale predpoklada ze osy obou sour. systemu sou rovnobezne, zistil sem vsak ze mapa je asi o 0.5stupne pootocena...

BTW mozna by stacily jen 3 body, ale asi by musely tvorit pravouhly trojuhelnik..

EDIT:
Aby to bylo jasny, tak tady este nacrtek (znam x1-4,y1-4 a jejich obrazy, hledam funkci f)

Idealni by byl zdrojak v C ale postaci nejaky odkaz kde se tohle resi, zatim sem nic rozumnyho nenasel.

[RayeR]

Tak uz zhruba vim jak na to, jen este nakej alg. na spocteni inverzni matice 9xn

[Warran]

Pokud si dobře vzpomínám na algebru, tak inverzní matice existuje jen ke čtvercové , protože matici a inverzní matice musejí být navzájem vynásobitelné, což je u čtvercových zaručeno.
Jeden postup je:
napsat si vedle matice jednotkovou
původní matici Gaussovou eliminační metodou upravit na jednotkovou a stejné operace provádět s tou druhou. Výsledkem je, že z původně jednotkové matice se stane inverzní.
Tady jsem vygooglil popis
http://www.kolej.mff.cuni.cz/~lmotm2...ml/node55.html
Je tady uvedený i druhý způsob přes determinanty, ale počítat determinanty matice rozměru +-9 je IMHO blbost, složité a dlouhé. Šel bych první cestou.

Kdyby byl zájem můžu se mrknout, jestli ještě najdu skripta, pak bych je naskenoval.

for (radek = 0; radek < n; radek ++) { /* projit vsechny radky */
   pivot = matice[radek][radek];
   for (i = 0; i < n; i++)
      matice[radek][i] /= -1 * pivot;    /*vyrobit jednicku na miste na hlavni diagonale */
   
   for (i = radek; i < n - 1; i++) {       /* projdu vsechny nizsi radky mimo posledniho */
      pivot = matice[i + 1][i] / matice[i][i] * -1;  /* cislo, kterym musim vynasobit radek a pricist k nizsimu radku */
      for (j = 0; j < n; j++) {  /* tady nasobim ten radek a pricitam ke spodnimu */
         matice[i + 1][j] += matice[i][j] * pivot
      }
   }
}

/* opakovat cele obracene, to jest odspoda nahoru a vytvaret nuly nad hlavni diagonalou. Ty same operace provadet s tou druhou matici */

Je to jenom takovy lehoučký nástřel pro inspiraci, kdoví jestli by někde nějaký index nepřetekl apod. Možná je tam i logická chyba. Kdo ví . Ale zhruba takhle se to dělá.

[Haste]

Jenom bych podotkl, ze vypocet pres determinanty neni obecne slozitejsi. Mnohdy (u "nehezkych" cisel nebo u matic s neznamyma) je to vyhodnejsi nez pres jednotkovou matici. Navic u algoritmizace jsou potom determinanty/subdeterminanty zasadni.

[Warran]

Jenom bych podotkl, ze vypocet pres determinanty neni obecne slozitejsi.

To je velká pravda.
Ale dodal bych, že než se člověk dostane na matici 3x3, tak v případě matice 9x9 to bude patrně několik rekurzivních volání. Pokud si dobře vzpomínám, tak spočítat determinant matice n x n, kde n > 3 znamená spočítat 1 determinant matice n x n a n-1 determinantů matice rozměru n - 1. A pro každou to takhle rozvíjet až do řádu 3x3. Takže to narůstá neskutečným tempem a trvalo by to neskutečně dlouho. Učitel matematiky nám jednou demonstroval, že počítat takhle determinant matice 100x100 by i nejvýkonějšímu superpočítači trvalo miliardy let (možná desítky miliard).
Pro matici 9x9 to myslím znamená následující:
-1x determinant matice 9x9
-8 x determinant matice 8x8
(snad jsem to řekl dobře, nechce se mi hledat skripta z algebry).
Leda by se ty determinanty počítaly jinak (úprava na dolní trojúhelníkovou a pak vynásobit prvky na hlavní diagonále ??), ale to je pak rovnou možné počítat tu inverzní matici tou první metodou.

[RayeR]

Diky,
uz sem sehnal nakej C kod na inv. matice, sou tam hned 2 algoritmy: Gauss routine a Crout routine. Gauss ma bejt rychlejsi a mene presnej, v praxi matice 1000x1000 trvala 0,4s a rozdil chyby byl par chlupu na poslednim desetinnym miste.

K ty matici m*n, pry existuje neco jako pseudoinverzni matice, ktera je prave pro obdelnikovy a pocita se: (AT*A)^-1*AT (kde AT je transponovana k A)

[Kon]

mi neni jasne to zadani. to jsou ctyri body nebo co ?

[RayeR]

mi neni jasne to zadani. to jsou ctyri body nebo co ?

Obrazek uz sem odmazal, neb ti co k tomu meli co rict uz rekli, naky algoritmy mam na papire, ale momentalne neni cas si s tim hrat.
Jak bylo zmineno vyse, slo o to najit matici zobrazeni pomoci ctyr (+-) kalibracnich bodu u nich znam vzor i obraz, tak abych mohl prepocitat souradnice libovolneho bodu na nove transformovane souradnice. Zobrazeni ma zohlednit rotaci a zmenu meritka na osach, v obou soustavach sou souradnice ortogonalni.

[Kon]

pokud jsou soustavy ortogonální, pak nechápu proč máš 4 body

[RayeR]

pokud jsou soustavy ortogonální, pak nechápu proč máš 4 body

No vsak sem psal, ze by mozna stacily 3. Ten algoritmus co sem sehnal tak bere obecne 4 a vice bodu, takze zvladne korikovat i dalsi deformace, coz se muze v budoucnu hodit...

[Kon]

no pokud mas univerzalni algoritmus pak jo, muze to byt zese na ukor rychlosti.
Jinak v ortogonalnim systemu vzhledem k jinemu muze dojit k posunu, otoceni, zmene meritka takze tech bodu moc nepotrebujes ... staci ti pracovat s maticemi 2x2

[RayeR]

No tak muzes nahodit tu zjednodusenou variantu, ale asi to uz udelam rovnou poradne, o rychlost az tak nejde prepocitava se jen pri pohybu mysi nad mapou.

[Haste]

No tak muzes nahodit tu zjednodusenou variantu, ale asi to uz udelam rovnou poradne, o rychlost az tak nejde prepocitava se jen pri pohybu mysi nad mapou.

Kdyz si vemem v potaz rychlost poolingu nekterych mysek, tak to muze byt i problem. Hodne Razeru/Logitechu mivaji pooling 250-1000Hz a to uz se projevi. Bys tam mel dat spis fixed timing, aby nedochazelo ke zpomaleni. Ale to jen tak na okraj...

[RayeR]

No jedna vec je jak windows rychle cte pozici z mysiportu a druha vec jak rychle se stiha vykreslovat kurzor nebo cokoliv na obrazovce, coz bude tak o rad min (vsync) jak ten 1kHz, ale i tak myslim ze to jeden vektor s matici stihne nasobit mnoohem rychleji.

[Haste]

No jedna vec je jak windows rychle cte pozici z mysiportu a druha vec jak rychle se stiha vykreslovat kurzor nebo cokoliv na obrazovce, coz bude tak o rad min (vsync) jak ten 1kHz, ale i tak myslim ze to jeden vektor s matici stihne nasobit mnoohem rychleji.

U WinAPI nejde o vsync. Zpravy ti do smycky chodi na MouseMove a to je opravdu az 1000x za sekundu podle poolingu. Vykreslovani kurzoru ve 2D je taky mnohem rychlejsi nez jak si myslis, pokud tedy jde o HW kurzor, ktery dnes vyuzivaji vsechny GK, ale opravdu tady nejde jeho vykresleni, ale o pocet zprav ve smycce. Podle me bys mel lepsi, kdybys to dal na wm_paint ci neco podobneho a nechal tam navic jasny interval. Treba 1/60 sekundy.

[RayeR]

No to je stejne fuk, protoze nepisu pro winy asi sem nemel to slovo vyslovovat

[Haste]

No to je stejne fuk, protoze nepisu pro winy asi sem nemel to slovo vyslovovat

To si nemel Jenom me to tak napadlo, ze by to zpomalovalo. Neco podobneho sem kdysi resil v nasem editoru.