rekensom in C

Ik heb het al eerder gezegd: In de tijd van de apollo11 moesten ze met een super-minimaal computertje de raket op koers houden. Daar zijn wat manuren in gaan zitten om dat passend te krijgen.

Als je een miljoen van jou apparaten gaat maken, ook dan is het interessant om het met de kleinste processor mogelijk te doen, zodat je niet miljoenen weggooit door een $5 duurdere processor te gebruiken.

Dat is allemaal niet meer van toepassing. Voor twee tientjes heb je een machientje met een halve gigabyte RAM d'r in. Wat nou extern ram?

Ik was even begonnen om toch even een bitmap manipulatie bibliotheekje voor je te schrijven. Maar met "extern RAM" en "geen malloc" en ... alllemaal compleet nutteloze beperkingen die JIJ JEZELF oplegt heeft het helemaal geen nut.

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

Golden Member

Is dat plaatje de vraagstelling? Wat zijn die 1000 en 2000 rijen en die kolommen dan? Missen we hier iets?

trix

Golden Member

het liefst zou ik natuurlijk de data zo "scannen":

1: 1000 (bit 0) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
2: 1000 (bit 1) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
3: 1000 (bit 2) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
4: 1000 (bit 3) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
5: 1000 (bit 4) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
6: 1000 (bit 5) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
7: 1000 (bit 6) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 1415.....T/M.....300
8: 1000 (bit 7) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300

9: 1000 (bit 0) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
10: 1000 (bit 1) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
11: 1000 (bit 2) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
12: 1000 (bit 3) ------- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.....T/M.....300
enz.
enz.

maar dan moet ik:
eerst 1 volledige byte uit de ext.RAM halen, dan bit 0 isoleren, kijken of hij "1" of "0" is.
2e volledige byte uit de ext. RAM halen, weer bit isoleren kijken of hij "1" of "0" is.
enz. enz. waarschijnlijk word het dan te traag.

eigenwijs = ook wijs
trix

Golden Member

post gekruisd.

die 1000, 2000, 3000, enz
zijn de begin adressen in de ext. RAM voor iedere horizontale rij.
dus 1001 t/m 1300
2001 t/m 2300
3001 t/m 3300

ik wil en ik ga ook naar een processor toe met voldoende interne RAM.
alleen is dat omzetten een heel gedoe, die tijd heb ik nu niet daarvoor.

in het begin dacht ik dat zo'n ext. ram geen problemen zou geven, en dat heeft het toe nu toe ook niet gedaan, lezen/schrijven geen enkel probleem.
alleen nu ik bit voor bit zou willen kijken loop ik tegen de beperking dat je alleen een volledige byte uit die ext. RAM kan halen, waar je vervolgens weer 1 bitje moet uit halen.
maar met een interne RAM moet je dat waarschijnlijk ook, alleen dan zijn de lees acties sneller.

eigenwijs = ook wijs
Hoeben

Golden Member

Je moet altijd een byte eruit halen. Alleen de oude 8051 familie kon je met bits werken.

Heel de vraagstelling is nog steeds wazig.

Arco

Special Member

De vraagstelling is inderdaad nogal cryptisch, maar komt volgens mij neer op:
"Waar binnen het grote vierkant bevindt zich het kleine vierkant?" (je wilt de hoekpunten van beide vierkanten)

Aangenomen dat er inderdaad 2 vierkanten zijn die zich netjes gedragen. (vierkanten kunnen ook gedraaid t.o.v. elkaar zijn of trapeziumvormig)

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

Golden Member

OK,dat gaat met een interne RAM het zelfde, de winst zit hem dan alleen in de tijd (snellere lees acties).

de oorspronkelijk vraag was ook anders, maar ik ben nog steeds zoekende naar een juiste methode, dus elke hulp word enorm gewardeerd _/-\o_

ik zal het probleem zo duidelijk mogelijk proberen te schetsen, dat is nog niet zo eenvoudig gebleken.

voorgaand plaatje heb ik een klein beetje aan gepast, adress vert. begint nu op 0 (i.p.v. 1000) en ik heb de regels een nummer gegeven voor de duidelijkheid.

- het plaatje geeft een mogelijke inhoud van de ext. RAM (is afkomstig van een scanner die al werkt).
- nu moet ik de coordinaten van alle binnen & buiten hoeken weten van dat rode ding (8 in totaal in dit geval).
- hier wil ik de inhoud bit voor bit aflopen en kijken naar de status ("0" of "1")
- te beginnen met pos. 1,1
- dan 1,2 1,3 1,4 1,5 1,5............1,298 1,299 1,300
- dan 2,1 2,2 2,3 2,4 2,5............2,298 2,299 2,300
- en zo de volledige inhoud van de ext. RAM
- aan de hand van al die "1"-en kan ik de hoeken bepalen.

meer is het niet.
alvast bedankt

eigenwijs = ook wijs
big_fat_mama

Zie Paulinha_B

Ge wilt toch maar een matrix declareren, twee-dimensionaal, en die dan doorlopen met twee lussen, eentje voor de x-as en de andere voor de y-as?
Wat is daar moeilijk of ingewikkeld aan?

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

Golden Member

precies,

bij die voor de Y-as moet je iedere keer een volledige byte uit de RAM halen, en die dan ontleden in losse bits.

als dat gelukt is, ga je zoeken en vind je ergens een "1".
daar zijn er mischien we 700 van. dus ga ik meteen kijken of dat een hoek kan zijn.
ik kijk of de onder buurman "1" is, indien ja
ik kijk of de rechtse buurman "1" is, indien ja
ik kijk of de rechtsonder buurman "1" is.
nou dit is dus de linker boven hoek.

dan ga je verder zoeken met dezelfde methode naar de rechter bovenhoek
vervolgens:
links onder
rechts onder
binnenhoek links boven
binnenhoek rechts boven
binnenhoek links onder
binnenhoek rechts onder

dat is een heel gedoe binnen in die lussen, waardoor het lastig is om het overzichtelijk te maken.

eigenwijs = ook wijs
Arco

Special Member

Met 1 byte ontleden kom je er niet: de hoekpunten kunnen ook precies op de overgang van 2 bytes zitten...
(je moet dus ook de inhoud van omliggende bytes erbij betrekken)

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

En een echt plaatje van de scanner is nooit zo strak als het voorbeeld hier. Als je dat ook mee wilt nemen is het echt niet meer zo gemakkelijk.

Ik heb hier ooit al een antwoord op gegeven, zo'n 7 maanden geleden:

dus je hoeft helemaal niet bit voor bit te werken. Als een byte de waarde 0 heeft, kun je direct door naar de volgende byte.
kun je hier wat mee??

Op 7 juni 2020 18:02:31 schreef Progger:
openCV kan dit op de PC realtime.
ik had de positie van een circel nodig, was 2 regels code.

[...]

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.

GMT+1
trix

Golden Member

gekruisd
klopt allebei, (arco & dekees)

Op 30 januari 2021 17:04:17 schreef Arco:
(je moet dus ook de inhoud van omliggende bytes erbij betrekken)

dat doe ik dus ook, zie mijn vorige post.

Op 30 januari 2021 17:12:16 schreef deKees:
En een echt plaatje van de scanner is nooit zo strak als het voorbeeld hier. Als je dat ook mee wilt nemen is het echt niet meer zo gemakkelijk.

dat niet strakke haal ik er dus uit door meteen de buurbits mee te testen, dan is een verdwaalde bit geen probleem.

Op 30 januari 2021 17:04:17 schreef Arco:
de hoekpunten kunnen ook precies op de overgang van 2 bytes zitten...

dit is een heel gedoe.
daarom is het ook zo lastig dat er meteen een byte uit de RAM komt i.p.v. losse bits.

al moet ik zeggen dat de scanner toch wel strakke plaatjes geeft :P

@progger, ik begrijp hier uit dat dit met een PC werkt, is dat correct ?

[Bericht gewijzigd door trix op zaterdag 30 januari 2021 18:07:02 (16%)

eigenwijs = ook wijs
Arco

Special Member

Je kunt veel gereken besparen door het logisch aan te pakken.

Je leest een horizontale regel vlnr in byte voor byte. Is de byte 0xFF dan meteen naar de volgende. Is de byte niet 0xFF dan heb je de linkerzijde gevonden.
Verdergaan tot je weer 0xFF krijgt, dan heb je de rechterzijde gevonden.

Een byte teruggaan en die hele (byte)kolom vertikaal testen naar boven en beneden tot je weer 0xFF krijgt. Je hebt dan boven/onderzijde.

Spaart testen van heel veel bytes en bits...

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

Golden Member

waar je 0xFF zegt bedoel je denk ik 0x00.

Een byte teruggaan en die hele (byte)kolom vertikaal testen naar boven en beneden tot je weer 0xFF krijgt. Je hebt dan boven/onderzijde.

dan weet je in welke byte de boven en onderzijde zit, maar nog niet welke bit het is, daarvoor moet je wat extra doen. en met name dit, dat weer terug te voeren is op het feit dat je een complete byte uit de RAM krijg maakt het zo lastig.
dan kan je net op de overgang tussen 2 bytes zitten...........weer wat extra :(

eigenwijs = ook wijs

trix,

de code die ik omschrijf is in theorie op ieder platform te gebruiken.
in C zou het er zo uitzien:

c code:


//eigenlijk beide op 0 of 1 beginnen:
int kolom = 1; // we starten links boven
int rij=0; //dit is de byte, niet de pixel
const int offset_per_rij = 1000;
const int aantal_kolommen = 300;
const int aantal_rijen = 38; 

bool found = false;

while(!found) do
{
    //als we aan het eind van de rij zijn, gaan we door met de volgende rij. 
    //mischien kun je tijd besparen als je tijdens het inlezen markeert welke rijen leeg zijn
    if (rij >= aantal_rijen)
    {
        kolom+=1;
        rij=0;
    }
    // het ophalen van de specifieke byte zul je in een losse functie moeten doen
    byte x = haal_byte_uit_ram(offet_per_rij * rij + kolom);
    if (x != 0) //8 rijen zijn niet leeg
    {
        p = bepaal_eerste_pixel(x)
        found=true;
    }
}
printf("gevonden op %d,%d",kolom,rij*8+p);

function bepaal_eerste_pixel(byte x)
{
    //bit 0 is de eerste pixel. bit 0 heeft waarde 1 (2¹=1)
    //dus als bit 3 t/m 5 hoog is willen we alleen bit 3 weten
    //en moeten we 2³ dus 3 maal door 2 delen.
    int pixel = 0;
    while (x%1==0) //zolang bit 0 laag is
    {
        x=x>>1 // naar rechts schuiven is delen door 2
        pixel +=1
    }
    return pixel;
}

zoals je ziet is het functie voor het vinden van de pixel maar 4 of 5 regels, klein beetje aanpassen voor de onderste hoek.
ik snap niet echt waar je op vast loopt?

het voorbeeld van OpenCV is inderdaad gebaseerd op de PC.

GMT+1
Arco

Special Member

Het bit weet je al van het testen in de horizontale rij. En vertikaal is de eerste 0xFF die je tegenkomt de rand van het vierkant.
Je spaart dan denk ik in totaal meer als 99% rekenwerk uit...

dan kan je net op de overgang tussen 2 bytes zitten...........weer wat extra

Als horizontaal een byte 0xff is, en het volgende is 0x00, dan weet je toch al dat je op de rand van het vierkant zit?

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

Golden Member

Op 30 januari 2021 19:56:57 schreef Arco:
Het bit weet je al van het testen in de horizontale rij. En vertikaal is de eerste 0xFF die je tegenkomt de rand van het vierkant.

nee, die bovenkant valt ergens midden in een byte, ergens moet je dus een byte "ontleden" om te kunnen zien welke bit dat nu precies is.

de buitenhoeken heb ik al werkend, moet nog wat extra testen. ik ben nu met de binnenhoeken bezig. als voorbeeld had ik een figuur met 4 binnenhoeken, maar er kunnen ook meer binnenhoeken zijn.

progger, ik moet het nog goed op me laten inwerken, mijn programeer skils zijn niet zo geweldig ;)

[Bericht gewijzigd door trix op zaterdag 30 januari 2021 20:23:39 (39%)

eigenwijs = ook wijs

Voor de binnenhoeken kun je beter kijken naar de buitenhoeken van die binnenruimte, dat doe je op dezelfde manier en met wat handigheid in dezelfde loop.

Arco

Special Member

nee, die bovenkant valt ergens midden in een byte, ergens moet je dus een byte "ontleden" om te kunnen zien welke bit dat nu precies is.

Ja, uiteraard.
Maar 't maakt nogal heel veel verschil of je 2 bytes moet ontleden of alle bytes van die matrix...

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

Golden Member

ik ontleed ze ook pas wanneer er aanleiding toe is.
ik heb straks even geprobeerd om elke bit uit een byte te halen, en zo bit voor bit het hele matrix af te scannen. dat is dus 300x300 = 9000 keer 1 bit uit een byte halen en beoordelen. dat duurde 25 sec.

eigenwijs = ook wijs

ALS je een bitmap in wat voor geheugen dan ook gaat opslaan dan doe je gewoon 8 bits in een byte. Die byte zit dan gewoon "horizontaal" in je plaatje.

code:

   byte1 byte2 byte3... 
   byte38 byte39....

Om een pixel te zetten doe je dan:

c code:


#define XSIZE 300
#define YSIZE 400
#define PITCH ((XSIZE+7)/8)

void set_pixel (x, y)
{
  memory[y*PITCH + x/8] |= 1 << x%8;
}

void clr_pixel (x, y)
{
  memory[y*PITCH + x/8] &= ~(1 << x%8);
}

int get_pixel (x, y)
{
  return (memory[y*PITCH + x/8] >> (x%8)) & 1;
}

Mijn PC is in ongeveer 1 tot 1.2 ms klaar met een scan van alle 300*300 pixels.

Mijn pi3 doet er ongeveer 8 ms over. Een pi vier doet er 4.1 tot 4.4 ms over.

Weet je wat? Ik ga met m'n raspberry pico proberen te spelen. Goede oefening voor me. Kijken wat die er van bakt.

Update: De 133MHz pi pico gaat in 4.5 sec zo'n 1000x door de array heen. Ongeveer even snel als de pi 4: rond de 4.5 ms per iteratie.

Dus even voor de goede orde: Wat jij hebt gemaakt is ongeveer 5000 keer langzamer dan wat ik heb gemaakt. Dat zal voor een belangrijk deel te maken hebben met dat jij extern RAM gebruikt. Dat is langzaam. (vandaar ook dat de ($40) pi4 maar net wint van de ($4) pico) Die pico is met 256k RAM dus een "redelijk geschikte microcontroller" voor deze toepassing.

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

Golden Member

Ik zou helemaal niet de hoeken zoeken.

Je moet bij wazige plaatjes (dat is ruis) zoveel mogelijk van het signaal zien te gebruiken. Die lange zijden van het object bevatten veel meer informatie dan het enkele bitje van de hoek.

Doe wat ik vroeger als colruler en rowruler gebruikte in de oude Philips SBIP kaart:
Neem een horizontaal lijntje en meet de overgang van donker naar licht. Je krijgt een array met X en X. Dat is een zijde van je object, een rechte lijn. Die lijn heeft als functie Y=AX+B. Dan doe je met de least-squares methode een curve-fit over dat array (google maar).

Doe dit voor alle zijden. Dan heb je de 4 zijden, de hoeken liggen op de kruispunten van de lijnen. Het grote voordeel is dat de least-square een mooie statistische fit heeft gemaakt over de hele lengte in plaats van alleen een punt en daarmee de ruis onderdrukt.

Een beetje herkenningssoftware doet tegenwoordig een 2D-fit en geeft je zo de positie en hoek. O.a. in elektronicaproductie zit het hier vol mee om componenten op de juiste positie op een PCB te kunnen zetten.

Edit: men beschuldigt mij er wel eens van anders te denken dan anderen...

Op 30 januari 2021 20:16:47 schreef trix:
[...]ergens moet je dus een byte "ontleden" [...]

progger, ik moet het nog goed op me laten inwerken, mijn programeer skils zijn niet zo geweldig ;)

die code ontleed dus een byte, en is maar 5 regels (excl commentaar), dus schrijf even goed op wat je niet begrijpt.
als je alles begrijpt, leg dan in je eigen woorden uit wat de code doet.

dat leert denk ik het snelst :)

GMT+1
trix

Golden Member

REW zegt:

Dus even voor de goede orde: Wat jij hebt gemaakt is ongeveer 5000 keer langzamer dan wat ik heb gemaakt.

nee, dat was dus een test af te leiden uit:

Op 30 januari 2021 21:42:28 schreef trix:
ik heb straks even geprobeerd om elke bit uit een byte te halen,

dat duurde inderdaad 25 sec.

ik zit nu op een scan tijd van ca. 800 mS. meeeeeeeer dan snel genoegvoor mijn toepassing :)

eigenwijs = ook wijs