www.mikrocontroller.net

Forum: Digitale Signalverarbeitung / DSP Pixel sortieren


Autor: Pixel sortieren (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,
ich habe eine Kette von ca. 1000 Pixeln (1000 x/y-Paare), von denen je 
zwei entweder seitlich oder diagonal miteinander verbunden sind, wie 
hier:

........
.1..45..
..23..6.
.....7..
........

Gibts da einen einfachen Algorithmus, die Pixel von einem zum anderen 
Ende durchzunummerieren, möglichst fertig in Matlab (zum Testen, wird 
später im Video-DSP implementiert)?

Mein Ansatz wäre, mit einem beliebigen Pixel anzufangen und sich in 
beiden Richtungen die Kette entlanghangeln, Aufwand O(N^2). Wäre 
zeitlich noch akzeptabel - gibts dafür eine Matlab-Funktion?

Evtl. gehts schneller als O(N^2), wenn z.B. abwechselnd nach x und y 
sortiert wird und dann jeweils Segmente gebildet werden, in denen 
entweder x oder y monoton steigt, aber ich sehe noch nicht, wie das im 
Detail implementiert werden könnte.

Seb

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also die Kurve bewegt sich wie der König im Schach, es gibt 8 erlaubte 
Züge, aber das Pixel von dem man kommt und seine beiden 
Nachbarpositionen sind tabu. Bleiben also 5 mögliche Nachbarpunkte, auf 
denen es weitergehen kann.

Um den richtigen zu ermitteln soll jetzt eine - möglicherweise 
vorsortierte - Tabelle nach diesen 5 x/y-Paaren durchsucht werden.

Habe ich die Aufgabe so richtig verstanden?

Autor: arc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn genügend Speicher zur Verfügung steht, könnte man das
in O(n) lösen:
Idee: Man erstellt ein Array mit der Größe des umschließenden Rechtecks
und kennzeichnet darin jeden Punkt aus der Eingangsliste (z.B. ptr/null 
oder als Index in die/das Eingangsliste/array).
Dann die Startposition suchen: Einfacher Durchlauf durch die 
Eingangsliste und den Punkt merken, für den gilt p.x = min({p.x}) und 
p.y = min({p.y}). Hat man den Startpunkt, kann man dann die jeweiligen 
Nachbarn überprüfen und den letzten Startpunkt löschen. Mit dem nächsten 
Punkt geht's dann weiter (nextInGrid)

Hat man weniger Speicher, erstellt man statt des Arrays eine Liste mit 
Listen (C++ z.B. mit STL: list<list<Point>>).

Pseudocode...
enumerate(points: list of point)
  // array mit Zeigern oder mit den Indizes der Eingabeliste
  grid: array[minX..maxX, minY..maxY] of ptr to point
  res: list of point

  // Punkte im Grid anordnen und 
  // T = n
  foreach p in points
    grid[p.x, p.y] = addr(p)
  
  // Startposition in der Liste mit Punkten suchen
  // kleinstes x und kleinstes y
  // T = n
  sx, sy = findStartPos(...)

  // eigentlicher Durchlauf 
  nextInGrid(sx, sy, grid, |points|)

nextInGrid(sx, sy, grid, remaining)
  // "gefundenen" Punkt speichern
  results.add(grid[sx, sy])
  remaining--;

  // rechter oder linker Nachbar 
  if grid[sx + 1, sy) not empty 
     nextInGrid(sx + 1, sy, grid, remaining)
  else if grid[sx - 1, sy] not empty
     nextInGrid(sx - 1, sy, grid, remaining)
  else if grid[sx + 1, sy + 1] not empty 
     nextGrid(sx + 1, sy + 1, array, count);
  else 
     // die restlichen Nachbarn 
     if grid[sx + 1, sy - 1] not empty
        nextGrid(sx + 1, sy - 1, array, count)
     else if (array[sx - 1, sy + 1] not empty
        nextGrid(sx - 1, sy + 1, array, count)
     else if (array[sx - 1, sy - 1] not empty
        nextGrid(sx - 1, sy - 1, array, count)
   

"Speicheroptimierte"-Variante O(n) = n log n
enum2(points: list of point) 
  grid: list of list of point

  // Liste(n) aufbauen T ~ n log n 
  foreach p in points
    // Suche ob schon eine Liste für die X-Koordinate vorhanden ist
    pos = binarySearch(grid, p.x) 
    if pos in grid
       // Punkt in die Teilliste einfügen
       grid[p.x].add(p)
    else 
       // neue Teilliste erzeugen
       grid.insert(p, pos) 
      
   // Startposition T ~ n
   sx, sy = findStartPos(...)
   // Durchlauf
   nextInGrid2(...)

nextInGrid2(sx, sy, grid, remaining)
  results.add(grid[sx][sy])
  // Punkt aus der Liste bzw. Teilliste entfernen
  grid.remove(sx, sy)
  remaining--;

  // die einfache Überprüfung wird hier durch eine Binärsuche ersetzt
  // linker Nachbar 
  // X-Position 
  posX = binarySearch(grid, p.x - 1)
  // Y in der passenden Teilliste suchen, falls diese existiert
  if posX != -1
     posY = binarySearch(grid[p.x], p.y)
     if posY != -1 
        nextInGrid2(posX, posY, grid, remaining) 
  end
  // und die restlichen Nachbarn überprüfen

  

Autor: Sebastian (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>in O(n) lösen:
>Idee: Man erstellt ein Array mit der Größe des umschließenden Rechtecks

Jaja. Rechteck hat O(N^2) Pixel. Guter Vorschlag.
Nächster Vorschlag?

Autor: arc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann entweder die zweite Lösung oder man implementiert eine etwas 
aufwendigere Planesweep/Scanline-Lösung

Autor: Christoph Kessler (db1uq) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
x und y-Koordinaten in einer Zahl zusammenfassen, z.B. y höherwertiger 
Teil.
Diese 1000 Zahlen aufsteigend sortieren. Mit sukzessiver Approximation 
mit je 10 Vergleichen können die 5 Nachbarpixel in der Tabelle gesucht 
werden, einer der 5 muß enthalten sein, der Rest nicht. Also ist im 
Schnitt nach 25 Vergleichen der Nachbarpunkt gefunden.

Autor: Detlef _a (detlef_a)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, Punkte sortieren geht mit O(n*log(n)) und in der Tabelle suchen mit 
O(log(n)), müßte doch eigentlich insgesamt mit O(n*log(n)) gehen, oder 
nich?

Cheers
Detlef

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.