3. Algoritmer som er utviklet i dette prosjektet
3.2 Algoritmer for å fastsette pikselstørrelsen i romkoordinater
Formålet med algoritmene som er beskrevet i dette kapittelet, er å finne hvor stor avstand en piksel i bildet representerer i romkoordinatsystemet. Det er laget algoritmer som baserer seg både på single QR-koder og som funksjon av flere.
Alle algoritmene er basert på å finne en linje mellom to punkter. Algoritmene finner avstanden mellom to punkter i bildet oppgitt i piksler. Den finner også avstanden i QR-matrisen oppgitt i millimeter. Pikselstørrelsen er da avstand i millimeter delt på avstand i piksel. Heretter nevens disse verdiene som mm-verdi og pikselverdi.
3.2.1 Snitt av linjer for pikselstørrelse
kodene er kvadratiske og dimensjonen i millimeter er et av parameteren som blir lest fra QR-koden. ZBar finner punktet til hver av de fire hjørnene i QR-koden oppgitt i piksler.
Denne algoritmen er delt opp i tre deler og leverer tre resultater for hver QR-kode. Den først delen bruker de fire linjene mellom de fire hjørnene som pikselverdi og den leste dimensjonen som mm-verdi. Et gjennomsnitt av pikselstørrelsen fra disse fire linjene blir returnert.
Den neste delen bruker de to diagonale linjene mellom motstående hjørner som pikselverdi.
Diagonalen i mm-verdi blir funnet ved Pytagoras setning med kateter lik den leste dimensjonen.
Gjennomsnitt av pikselstørrelsen fra disse to linjene returneres. Den siste delen returnerer et gjennomsnitt av pikselstørrelsen til alle de seks linjene fra de to foregående delene.
Relevant pseudokode er skrevet i Figur 18, og i kildekoden som ligger i vedlegg, kap. 7, er denne algoritmen implementert som ScanResults::getPixelSize_meanLines.
3.2.2 Lang linje for pikselstørrelse
Denne algoritmen finner, på samme måte som Lang linje for rotasjon i kap.3.1.3, den rette linjen mellom to QR-koder som ligger på linje i QR-matrisen, og som er lengst mulig fra hverandre. For å finne hvilke to QR-koder som skal brukes, er det satt noen kriterier:
• Det skal plukkes QR-koder fra den linjen hvor det er detektert flest QR-koder
• Hvis to linjer har like antall QR-koder, benyttes den linjen som ligger nærmest senter av bildet
• De to QR-kodene som ligger lengst fra hverandre på denne linjen skal brukes
Informasjon om hvilke koder som er på linje kalkuleres fra kodene sine koordinater i QR-matrisen. De blir lest fra datastrengen. Mm-verdien av linjen blir funnet som avstanden mellom disse punktene, og pikselverdien av linjen blir funnet som lengden av vektoren mellom de samme
hjørnene i bildet.
Relevant pseudokode finnes i Figur 19, og i kildekoden som ligger i vedlegg kap. 7, er denne algoritmen implementert som ScanResults::getPixelSize_longLine.
34
Figur 18. Pseudokode som viser hvordan pikselstørrelsen blir funnet ved hjelp av Snitt av linjer. Koden er relevant for kap.
3.2.1.
Figur 19. Pseudokode som viser hvordan pikselstørrelsen blir funnet ved hjelp av en linje. Koden er relevant for kap. 3.2.2, 3.2.3 og 3.2.4.
input: dim //QR-kodens fysiske størrelse i rommet corners[4] //QR-kodens fire hjønekoordianter i bildet Run{
//Linjer mellom hjønepunkt line1 = conres[0] - conres[1];
line2 = conres[1] - conres[2];
line3 = conres[2] - conres[3];
line4 = conres[3] - conres[0];
line5 = conres[0] - conres[2];
line6 = conres[1] - conres[3];
//Linjenes lengde
length1 = sqrt(line1.x2 + line1.y2 );
. .
length6 = sqrt(line6.x2 + line6.y2 );
//Pikselstørrelse for ytterlinjer pixsize1 = length1 / dim;
pixsize4 = length4 / dim; .
//Pikselstørrelse for diagonal pixsize5 = length5 / sqrt(2*dim2);
pixsize6 = length6 / sqrt(2*dim2);
return 1 mean(pixsize 1-4);
return 2 mean(pixsize 5-6);
return 3 mean(pixsize 1-6);
}
input: allQR_img // Vektor med alle QR-koder, for hver QR-kode brukes hjørne 1 i bildet allQR_room // Vektor med alle QR-koder, for hver QR-kode brukes hjørne 1 i rommet bool vertical // Valg om linjen skal være vertikal eller horisontal
// Merk at ved bruka algoritmen lengst mulig linje velges ikke retning, // if og else setningene utgår
Run{
if (vertical) {
sorted_QR = sortY(allQR_room); //Sorter alle QR-koder med lik Y verdi i grupper maxCount = max(sorted_QR); //Finn den gruppen med flest QR-koder
} else {
sorted_QR = sortX(allQR_room); //Sorter alle QR-koder med lik X verdi i grupper maxCount = max(sorted_QR); //Finn den gruppen med flest QR-koder
}
QRs_index[2] = choose(maxCount); //Velg ut to QR-koder som skal brukes til å //trekke en linje, valg er avhengig av algoritme line_img = allQR_img[QRs_index[1]] - allQR_img[QRs_index[2]];
line_room = allQR_room[QRs_index[1]] - allQR_room[QRs_index[2]];
length_img = sqrt(line_img.x2 + line_img.y2); //Lengden mellom QR-kodene i bildet length_room = sqrt(line_room.x2 + line_room.y2); //Lengden mellom QR-kodene i rommet return length_room/length_img;
}
35 Kapittel 3 Algoritmer som er utviklet i dette prosjektet
3.2.3 Kort linje for pikselstørrelse
Denne algoritmen finner, på samme måte som Kort linje for rotasjon i kap.3.1.4, den rette linjen mellom to QR-koder som ligger på linje i QR-matrisen og som er nærmest mulig senter av bildet. For å finne hvilke to QR-koder som skal brukes er det satt noen kriterier:
• Det skal plukkes QR-koder fra den linjen hvor det er detektert flest QR-koder
• Hvis to linjer har like antall QR-koder, benyttes den linjen som ligger nærmest senter av bildet
• De to QR-kodene på denne linjen, som ligger nærmest senter av bildet skal brukes Informasjon om hvilke koder som er på linje kalkuleres fra kodene sine koordinater i QR-matrisen. De blir lest fra datastrengen. Mm-verdien av linjen blir funnet som avstanden mellom disse punktene. Pikselverdien av linjen blir funnet som lengden av vektoren mellom de samme hjørnene i bildet.
Relevant pseudokode finnes i Figur 19, og i kildekoden som ligger i vedlegg kap. 7, er denne algoritmen implementert som ScanResults::getPixelSize_shortLine.
3.2.4 Lengst mulig linje for pikselstørrelse
Denne algoritmen finner linjen mellom de to QR-kodene som har størst avstand til hverandre. Dette kalkuleres med en iterativ fremgangsmåte. Hver kodes avstand i matrisen til alle andre QR-koder kalkuleres, og de to med lengst avstand til hverandre blir valgt. Pikselstørrelsen blir så kalkulert på lik måte som i kap.3.2.2 og 3.2.3.
Relevant pseudokode finnes i Figur 19, men her velges ikke noen retning som inngangsparameter. If og else setningene i figuren går dermed ut for denne algoritmen. I kildekoden som ligger i vedlegg, kap. 7, er denne algoritmen implementert som ScanResults::getPixelSize_longestPossibleLine.
36