coordinaten in een matrix vinden ?

trix

Golden Member

ik heb in een matrix van 300x300 bits een figuur bestaande uit allemaal "1"-en. opgeslagen in een externe RAM.
figuur bestaat enkel uit rechte lijnen. nu wil ik daar alle hoekpunten van gaan bepalen.

ik heb al 1 methode geprobeerd, maar die is naar mijn gevoel nogal omslachtig, en daarmee niet erg duidelijk.

weet iemand hoe je dit het best kan doen, of is hier een methode voor ?

alvast bedankt voor de reacties.

matrix is in werkelijkheid 300x300 bits.

eigenwijs = ook wijs
big_fat_mama

Zie Paulinha_B

Bestaat de figuur altijd uit een "zwart" vierkant of rechthoek, met een wit vierkant of rechthoek er binnen in? Dan lijkt het me niet al te moeilijk.

Als het bv. ook een witte zevenhoek kan zijn, omsloten door een zwarte negenhoek, dan ga ik eens in mijn schaarse haar krabben...

[Bericht gewijzigd door big_fat_mama op zondag 7 juni 2020 13:28:00 (31%)

hoe beter de vraag geschreven, zoveel te meer kans op goed antwoord
trix

Golden Member

nee geen 7 of 9 hoeken.
wel kunnen er meerdere rechthoeken binnen de buitenste rechthoek zitten.
ik zal daar ook eens een plaatje van maken.

eigenwijs = ook wijs
trix

Golden Member

eigenwijs = ook wijs

Als het altijd alleen zuiver horizontale en verticale lijnen zijn, is het niet zo moeilijk.

De hoekpunten zijn precies die pixels waarbij:

  • de bovenliggende of de onderliggende pixel gevuld is, maar niet allebei, en tevens;
  • waarbij de linkerpixel of de rechterpixel gevuld is, maar niet allebei.

edit: had geen rekening gehouden met de binnenhoeken. Dan zou ik buren gaan tellen (links/rechts, boven/beneden, en diagonaal). Met drie buren heb je een buitenhoek te pakken, met zeven buren een binnenhoek.

Je maakt een loop of scan van de 300 regels maal 300 kolommen. 90000 keer dus, dan zoek je de eerste 1 en de laatste 1 (gewoon de loop achterwaarts draaien)

(Als snelheid belangrijk is dan onthoud je deze coördinaten als startpunt voor de volgende acties)

Heb je de 1 gevonden dan zoek je of je minimaal X 1tjes ernaast en eronder hebt om ruis uit te sluiten.

De tweede stap:

Doe nu de kolommen maal regels. Zo scan je de meest linker en rechterzijde.

Als de rechthoeken altijd recht liggen dan ben je er al. Als er ruis, viezigheid, onregelmatige vormen of scheve rechthoeken zijn dan moet je wat marges doorlopen.

Edit: als de vormen echt altijd zo prefect zijn:

Zoek alle:

00
01

Blokjes dat zijn "linksbovens buitenkant"

Dan alle

00
10 (rechtsboven buitenkant)

Etc...

Pseudo code:

If x,y=1 and x-1,y=0 and x-1,y-1 and ....

[Bericht gewijzigd door K7Jz op zondag 7 juni 2020 14:02:14 (16%)

trix

Golden Member

mijn methode was om met een complete byte van links naar rechts te scannen. eerst zie je een hoop 0 bytes
zodra die niet 0 is, kijken of er 2 bits naast elkaar 1 zijn
dan een byte verder kijken of die 2 zelfde bits "1" zijn
zo ja, 1e buiten hoek (links boven) gevonden
een vlag zetten dat je die hebt gevonden.
en naar de rechter bovenhoek gaan zoeken.

alleen als je 1e niet 0 byte 0b00000001 is, moet je dus ook in de byte daaronder kijken (extra lees actie uit de RAM) en in de byte rechtsonder (weer een extra lees actie) leek mij nogal omslachtig.

dus ik denk ik ga bit voor bit van links naar rechts & van boven naar beneden het geheel "scannen" dan heb je niks van doen met de "naden" tussen de bytes.
alleen dan krijg je wel heel veel lees acties, minimaal 300x300 = 90000 keer.

de methode die ik nu heb (nog niet geheel klaar) doet er ong 5 sec. over om alles te scannen (8 Mhz). dat is acceptabel.

edit: het figuur ligt niet altijd zo perfect in de matrix, het kan er ook een beetje scheef inliggen. maar als ik dan de "grootste" maten heb is het goed.

eigenwijs = ook wijs

Wat is mis of of je weet waar het midden ligt. Is dat bekend?

In mijn oude Philips SBIP framegrabber tijd had ik dit zo opgelost met colruler en rowruler:

Scan van boven naar beneden waar de 1-en beginnen en eindigen. Dan heb je de Y-coordinaten.

Doe hetzelfde horizontaal, dan heb je de x-coordinaten.

Vind je niks of te weinig punten, probeer dan links of rechts.

trix

Golden Member

die methode is in gedachte ook voorbij gekomen, eerst de X-coordinaten en dan de Y-coordinaten.
van links naar rechts (X-coordinaten) is geen probleem, omdat de bytes in de RAM "verticaal" staan. maar van boven naar beneden (Y-coordinaten) is lastiger. je moet dan toch iedere keer een byte uit de RAM halen, en daar 1 bit uit isolereren, en dat 300 x voor 1 rij, dit maal 300 rijen is toch weer 90000 lees acties.

eigenwijs = ook wijs
benleentje

Golden Member

....

[Bericht gewijzigd door benleentje op zondag 7 juni 2020 16:47:21 (98%)

Mensen zijn soms net als een gelijkrichter, ze willen graag hun gelijk hebben.
benleentje

Golden Member

Zou het mogelijk zijn om eerst alle enen in het geheugen te mappen met de coordinaten. En daarna kijken voor aaneengesloten x of y coordinaten. Feitelijk ben je nu met video bewerking bezig wat sowieso altijd veel processor tijd en geheugen kost.

Mensen zijn soms net als een gelijkrichter, ze willen graag hun gelijk hebben.
trix

Golden Member

ik denk het wel, maar dat kost ook weer veel tijd.

eigenwijs = ook wijs

openCV kan dit op de PC realtime.
ik had de positie van een circel nodig, was 2 regels code.

kan deze situatie in mindere of meerdere mate ook optreden?
https://i.stack.imgur.com/K47w0.png

dan zou ik alles eerst naar de PC sturen voor het verwerken.

Op 7 juni 2020 16:03:20 schreef trix:
die methode is in gedachte ook voorbij gekomen, eerst de X-coordinaten en dan de Y-coordinaten.
van links naar rechts (X-coordinaten) is geen probleem, omdat de bytes in de RAM "verticaal" staan. maar van boven naar beneden (Y-coordinaten) is lastiger. je moet dan toch iedere keer een byte uit de RAM halen, en daar 1 bit uit isolereren, en dat 300 x voor 1 rij, dit maal 300 rijen is toch weer 90000 lees acties.

dit valt reuze mee, van links naar rechts hoef je inderdaad enkel te kijken of de byte > 0, dan is minimaal 1 pixel hoog.

van boven naar beneden haal je 1 byte op (1000) en kijk je of hij ==0, dan zijn alle pixels uit, dus:

byte is 0 --> geen pixels hoog, sla byte over
byte > 128? bit 7 is hoog
byte > 64? bit 6 is hoog
..
byte > 0? bit 0 is hoog

zo heb je de eerste zwarte lijn snel gevonden. als een byte geen pixels bevat heb je met 1 leesactie 8 pixels gehad.

[Bericht gewijzigd door Progger op zondag 7 juni 2020 18:12:04 (65%)

GMT+1
trix

Golden Member

ja dat is waar, checken of de byte 0 is,...zo ja, overslaan.

nee zo schuin nu ook weer niet....een beetje schuin. als je je voorsteld dat het plaatje met de 1e 4-kant 1 mtr. lang is, dan kan hij aan 1 kant zegt 4-5 cm. lager hangen.

[Bericht gewijzigd door trix op zondag 7 juni 2020 18:14:46 (16%)

eigenwijs = ook wijs

Er zijn héél veel truukjes om performance te winnen. Beginnen vanuit het midden bijvoorbeeld of een derde. Als je objecten minimaal 40 pixels zijn dan ga de eerste links en onder 30 niet scannen na een eerste hoek.

Je kan ook in steeds kleinere vierkanten scannen.

Alle 01 en 10 paartjes zijn interessant alles met alleen 0 of 1 kan je uit de set wissen. Je bewaart eigenlijk alleen de horizontale contrastlijnen (die lopen dus verticaal). Daarna moet je alleen nog de hoeken vinden, dat is altijd de hoogste 01 of 10 set, de laagste, de meest linker of meest rechter. Heb je twee hoogste en twer laagste dan ligt het perfect recht en is het rechthoekig.

Maar 90.000 bits, zeg 12kB, dat is met 10MHz toch in milliseconden gedaan?

trix

Golden Member

8 Mhz,
ik heb nu een 36 for-lus (36 bytes x 8 = 288 bits) met daarin genesteld een 300 for-lus. en die duurt ong. 5 sec.
heb er nog niet aan gerekend of echt over na gedacht.
het lijkt nu alsof snelheid het meest belangrijk is, maar het ging er mij ook over, of ik een methode over het hoofd zie, of domweg niet ken.

eigenwijs = ook wijs

Wat mij opvalt, is dat elk hoekpunt dat je wilt tellen een diagonale buurman heeft die 0 is. Wat ik zou proberen, is steeds een regel XOR'en met de regel erboven, 1 pixel verschoven; dat kun je per 32 pixels ineens doen, en als het resultaat 0 is, hoef je niet verder te kijken. Als het resultaat ongelijk is aan 0, moet je iets verder analyseren om te bekijken of het een gewenst hoekpunt is.

Als zo'n object scheef ligt, wil je dan alsnog de hoekpunten vinden, of de bounding box?

Als je meerdere objecten naast elkaar hebt, die ook nog eens scheef liggen, wordt het lastiger; dan zul je moeten bekijken welke hoekpunten bij één object horen. Je zou daarvoor een floodfill algoritme kunnen gebruiken.

Een manager is iemand die denkt dat negen vrouwen in één maand een kind kunnen maken
trix

Golden Member

stof tot nadenken.

een bounding box is goed inderdaad (een rechthoek getekend over de "grootste" coordinate.

eigenwijs = ook wijs

Op 7 juni 2020 16:03:20 schreef trix:
die methode is in gedachte ook voorbij gekomen, eerst de X-coordinaten en dan de Y-coordinaten.
van links naar rechts (X-coordinaten) is geen probleem, omdat de bytes in de RAM "verticaal" staan. maar van boven naar beneden (Y-coordinaten) is lastiger. je moet dan toch iedere keer een byte uit de RAM halen, en daar 1 bit uit isolereren, en dat 300 x voor 1 rij, dit maal 300 rijen is toch weer 90000 lees acties.

Het zijn maar een paar acties. Doe het volgende voor verticaal en horizontaal:

  • Lees bytes tot <> 0.
  • Bepaal welke bit aan is dmv shift right tot het byte 0 is, even meetellen.
  • Lees volgende bytes tot ze ongelijk aan $FF zijn.
  • Bepaal met dezelfde methode het laatste bit dat aan staat.
  • Herhaal dit alles, dan heb je alle 4 de punten.
  • En doe dit nogmaals voor de andere richting.

En als je de scheefstand wil meten zoek je het midden met de midpoint-methode (google maar) en meet een stuk naar links en een stuk naar rechts. Een beetje goniometrie helpt je dan wel verder.

Gewoon aan beginnen, is best eenvoudig bit-[censuur].

Je hoeft echt niet alles te meten als je toch al weet dat het een rechthoek is.

Arco

Special Member

Een camera met objectherkenning lijkt me een stuk simpeler... (heb alleen geen idee wat een goed systeem kost)

[edit]: 3D scanners zijn er al vanaf 450 euro: https://www.123-3d.nl/3D-Systems-Sense-2-3D-scanner-i3093-t15108.html?…

Arco - "Simplicity is a prerequisite for reliability" - hard-, firm-, en software ontwikkeling: www.arcovox.com

Ik denk dat ik weet over welk project het gaat en dat je onhandig bezig bent met een te kleine microcontroller.

Doordat je met een te kleine microcontroller bezig bent, ga jij je brein inzetten om over "bytes" en "waar in RAM" dingen staan, terwijl je met dit probleempje niet anders dan naar de bitjes en hun coordinaten wil kijken.

In jou "ideale" plaatjes zijn de hoekpunten die punten die PRECIES aan een patroon voldoen.

code:


int x,y, det_arr[16] = {0,1,1,0, 
                        1,0,0,1,
                        1,0,0,1,
                        0,1,1,0};
for (x=0;x<299;x++)
   for (y=0;y<299;y++) {
      pat = image (x,   y)   |
            image (x+1, y)   |
            image (x,   y+1) |
            image (x+1, y+1);
      if (det_arr[pat]) printf ("hoek op %d,%d\n",x,y);
   }

Dus dit vind conform je "opdracht" precies de punten die je gemarkeerd hebt.

four NANDS do make a NOR . Kijk ook eens in onze shop: http://www.bitwizard.nl/shop/
trix

Golden Member

inderdaad dat project.....nog steeds ;)

probeer je code te doorgronden, valt nog niet mee. pat & image is mij o.a. niet geheel duidelijk.

dat van hoebe vat ik ook nog niet helemaal, komt mischien nog.

@arco: die is geen 3 meter.

ga ik scannen op b.v. onderstaande patronen, dan zal een verdwaalde `0` of `1` bit ook een hoek kunnen zijn.

[Bericht gewijzigd door trix op maandag 8 juni 2020 19:37:24 (18%)

eigenwijs = ook wijs