Ideen für einen Algorithmus

[Schwachkopp]

Bitte ins Programmieren Forum verschieben.

Hallo,

ich suche Ideen und Anregungen für ein recht spezifisches Problem. Einen möglichen Ansatz habe ich schon gefunden, allerdings noch nicht sehr weit ausgebaut. Möglicherweise gibt es mir unbekannte Verfahren für sowas oder jemand hat einen besseren Vorschlag, so dass ich mir die Mühe sparen könnte meine Idee weiterzuentwickeln.


Hier das Problem:
Betrachtet wird ein Gitter in drei Dimensionen (Der Einfachheit halber hab ich das mal in 2D gemalt, siehe Bilder). Die grauen Kästchen kann man sich als Wände vorstellen, weiße Kästchen stellen den Außenbereich dar und hellblau den Innenraum. Die grauen Wände definieren also so eine Art Gebäude könnte man sagen. Es gibt Öffnungen nach draußen (sind unterschiedlich groß und zufällig verteilt), woraus sich ergibt, dass man Aussen und Innen nicht klar unterscheiden kann.

Dennoch ist genau das das Ziel. Ich suche ein Verfahren mit dem man Kästchen die zum Interieur gehören, identifizieren kann. Ein blaues Kästchen kann immer als gegeben angesehen werden (ist also schon als Innenbereich markiert). Das linke Bild entspricht dem idealen Ergebnis im Falle eine sehr einfach Geometrie (alle blauen Kästchen liegen tatsächlich im Innenraum aus Sicht eines menschlichen Betrachters sozusagen) und rechts ist das Ergebnis, was durch einen Algorithmus erzeugt worden sein könnte (durch die unklare Abgrenzung sind auch ein paar Aussenblöcke blau markiert).

Also noch mal, gesucht wird ein Algorithmus der eine ungefähre Unterscheidung von Interieur und Exterieur liefert. Die Größe und die Form des Hauses (graue Wände) sind mehr oder weniger beliebig, wobei man davon ausgehen kann das komplizierte Formen eher nicht auftreten. Die Öffnungen nach draußen sind beliebig verteilt und von unterschiedlicher Größe, allerdings relativ klein im Vergleich zu den Wänden.

So, ich hoffe das ist einigermäßen verständlich. Ich danke euch für die Antworten falls denn welche kommen.

Edit:
Der Algorithmus muss nicht immer das richtige, bzw. ein sinnvolles Ergebnis liefern aber in möglichst vielen Situationen. Außerdem muss das Verfahren nicht unbedingt deterministisch sein.

 

[Fu Manchu]

... ein Algorithmus der eine ungefähre Unterscheidung von Interieur und Exterieur liefert...

ungefähr? Du meinst eine genaue Unterscheidung .

Wäre es evtl möglich die Lücken durch den Algor. schließen zu lassen? Linien verbinden. Dann wären:
a) alle grauen, die vorher blau waren --> außen
b) alle blauen die von blauen umgeben sind --> iteration --> die von grauen umgeben sind --> innen

 

[Schwachkopp]

Die Lücken zu schliessen, klingt erstmal nach einer ziemlich guten Idee. Ich muss erst drüber nachdenken ... Bin dann später oder morgen wieder hier.

Hier ist mal ein Anfangszustand dargestellt zur weiteren Veranschaulichung:

 

[Homoioteleuton]

eine gute idee wäre, zuerstmal den schwerpunkt zu berechnen, damit man ne ahnung hat, wo ungefähr der raum liegt.
Außerdem könnte man für jeden Pixel, der keine Wand ist, in alle 4 Richtungen laufen und schauen, ob man irgendwann auf die Wand trifft.
Trifft man für alle Richtungen auf eine Wand, ist man innerhalb, wenn nicht, außerhalb.
Hierbei gibt es ne Menge Ausnahmen (zb deine Zugänge), also kann man die Bedingung vllt auf 3 Richtungen beschränken.
Außerdem kann man eventuell Pixel zusammenfassen, um die Rechenzeit zu verkürzen.

 

[4badd0n]

ungefähr? Du meinst eine genaue Unterscheidung .

Wäre es evtl möglich die Lücken durch den Algor. schließen zu lassen? Linien verbinden. Dann wären:
a) alle grauen, die vorher blau waren --> außen
b) alle blauen die von blauen umgeben sind --> iteration --> die von grauen umgeben sind --> innen

c) alle weißen Felder die jetzt an mindestens 2 Kanten an ein blaues Feld grenzen -> innen.

Denn beim Verbinden werden wohl auch Verbindungen innerhalb des Raumes entstehen und wären dann nach dem Auflösen weiß.

 

[Schwachkopp]

@Homoioteleuton

Ich vermute das mit dem Schwerpunkt könnte evtl. schiefgehen, jedenfalls wenn man nur 3 Richtungen berücksichtigt. Bin mir grad nicht sicher. Anderseits ist ja ein Innenpixel bekannt.

Hier liegt der Schwerpunkt ausserhalb oder nicht?

@Fu Manchu, 4badd0n
Ich glaub man findet Fälle in denen der Algorithmus das nicht vernüpftig schliessen würde.

 

[Homoioteleuton]

der schwerpunkt wäre nur für eine grobe idee, um sich etwas zu orientieren und unabhängig vom rest der methode.

sind es immer 4 Öffnungen? Damit kann auch arbeiten, indem man die grauen Pixel sucht, die nur einen Nachbarn haben

 

[Schwachkopp]

Es sind beliebig viele Öffnungen mit verschiedenen Größen. Allerdings sind die Öffnung relativ klein im Vergleich zur Wand bzw. man kann davon ausgehen, dass das Teil nicht zu sehr nach schweizer Käse aussieht. Ich weiß das ist alles etwas ungenau...

Den Schwerpunkt zu berücksichtigen könnte durchaus nochmal ein nützliches Puzzlestück werden. mhh

 

[Bunshichi]

Wahrscheinlich macht es Sinn, einen mehrstufigen Ansatz zu fahren. Zum Beispiel erst mal Object-Seperation betreiben und sich überlegen, wie man zusammengehörende Körper voneinander separiert.
Dazu hat eine kurze Google-Suche ergeben, dass es da wohl einige Whitepaper zu gibt. ZB "Recognition and separation of discrete objects within complex 3D voxelized structures" von Alexander Proussevitch Dork Sahagian.
Sobald zu eine Ahnung hast wo die einzelnen Körper liegen und am besten noch eine Konvexe Hülle drumrum vorliegen hast, kannst innerhalb dieser Hülle mit aufwändigeren Algorithmen beginnen um exakt zu bestimmen wo "drinnen" und "draußen" ist.
Es würde natürlich helfen, wenn du minima/maxima der Größe der Öffnungen nicht erst erraten musst, sondern weißt. damit kannst du diese dann einfacher ignorieren/schließen.

 

[4badd0n]

Gibt es denn irgendwelche definierten Einschränkungen bezüglich der Öffnungen, Form des Raums oder Innenwände?
Ansonsten glaube ich, dass man für alles ein Beispiel findet, wo der Algorithmus nicht mehr greift. Und genau so auch leicht Beispiele in denen für Menschen kein eindeutiger Raum erkennbar ist. Man stelle sich einfach nur einen sehr verwinkelten Raum mit mehreren Innenwänden und vielen großen Öffnungen vor und schon gibt es mehrere Lösungen, die der Algorithmus mit abdecken müsste.

 

[Schwachkopp]

Also im Moment benutze ich eine Art Random-Walk der vom ersten Innenraumpunkt aus startet und mehrmals durchgeführt wird. Es wird gezählt wie oft ein Kästchen betreten wird. Man sieht dann das die innenliegenden Kästchen häufiger betreten werden...

@4badd0n
Das stimmt natürlich. Das Verfahren kann nicht immer funktionieren aber 'oft' (werde das mal im OP ändern). Ich werde nachher mal versuchen ein paar sinnvolle Einschränkungen zu definieren. Obwohl das vermutlich ziemlich schwer sein dürfte.

@Bunshichi
Danke, das könnte das sein wonach ich gesucht habe. Oder wenigstens Ansätze liefern. Jedenfalls weiß ich jetzt wenigstens nach welchen Begriffen ich googlen könnte.^^

 

[Fu Manchu]

c) alle weißen Felder die jetzt an mindestens 2 Kanten an ein blaues Feld grenzen -> innen...

Nö, alle weißen Felder sind ja automatisch außen, siehe Ausgangslage. Es geht darum die blauen Felder zu prüfen.

...Ich glaub man findet Fälle in denen der Algorithmus das nicht vernüpftig schliessen würde.

Ein vernünftiger Algorithmus schon . Und du sagst ja, dass die Lücken klein sind. So wie in deinen Zeichnungen oder größer? In deinen Zeichnungen wären alle Lücken einfach zu schließen.

 

[new Account()]

Eventuell einen anderen Ansatz probieren: Außen statt innen finden.

Definitiv außen sind Geraden, die keine Mauer treffen.

Dadurch weißt du z.B., dass alle Punkte, die in der Kette "weiß|blau, grau, außen" definitiv innen sind.

 

[Bunshichi]

@Bunshichi
Danke, das könnte das sein wonach ich gesucht habe. Oder wenigstens Ansätze liefern. Jedenfalls weiß ich jetzt wenigstens nach welchen Begriffen ich googlen könnte.^^

Ich bin mir sicher, dass im Universum der Voxel-Techniken wirst mit einer Kombination von Algorithmen und Ansätzen fündig. Aber total trivial macht das dein Anliegen leider nicht. Ich glaube aber daran, dass alle deine Sub-Probleme die dein Hauptproblem ausmachen in der Domäne schon mal gelöst wurden. Divide-and-conquer

 

[florian.]

vielleicht den Ansatz:
Bin ich ein Loch? --> Loch schließen
alles was übrig bleibt ist innen.

 

[0-8-15 User]

Außen statt innen finden.

@Schwachkopp, das klingt auf den ersten Blick ziemlich vielversprechend. Was meinst du?

 

[striker159]

Wie wäre es, für jedes weiße Feld, dass zu einem blauen Feld benachbart ist, eine zufällige Anzahl an Strahlen in zufällige Richtungen zu schießen?
Wenn ein Strahl eine gerade Anzahl von grauen Boxen trifft nimmt man an, dass das weiße Feld außen liegt, sonst innen. Am Ende wählt man den Fall, der am häufigsten aufgetreten ist.

False Positives könnte man am Ende verbessern, in dem jedes weiße Feld, dass nur blaue und graue Nachbarn hat, auch blau gesetzt wird.

 

[Killkrog]

---

 

[kuddlmuddl]

https://de.wikipedia.org/wiki/Mathematische_Morphologie
mit dem https://de.wikipedia.org/wiki/Opening_(Bildverarbeitung) und was du suchst https://de.wikipedia.org/wiki/Closing.
Gibts hier fertig: https://docs.opencv.org/3.4/d9/d61/tutorial_py_morphological_ops.html einfacher sonst erstmal nur Dilation

 

[Schwachkopp]

@florian.
Ok, das ist trival machbar solange sich in der Nähe des Loches keine anderen Dinge wie Innensäulen oder andere Wände befinden. Muss mal schauen wie gut das geht.

@new Account(), 0-8-15 User

Definitiv außen sind Geraden, die keine Mauer treffen.

Klingt so ein bisschen nach konvexe Hülle suchen. Ja das kann als Zwischenschritt sicher nützlich werden.

@striker159
Mir fällt schwer einzuschätzen was dabei herauskommen würde. Wie man auf den ersten Bildern sieht, gibt es ja auch sowas wie Möbel bzw. Innensäulen. Die könnten dann False Positives auslösen wenn ich deinen Vorschlag richtig verstanden hab. Man müsste also schauen wie häufig das passiert und wie gut man diese Fälle erkennen kann.

@kuddlmuddl
Danke für die Links! Werde da mal reinschauen.

@All
Leider war ich wohl etwas zu voreilig beim Erstellen dieses Threads oder vielleicht auch nicht denn sehr hilfreich waren die Antworten ja. Dennoch, ich muss mir noch mehr darüber im Klaren werden was ich eigentlich benötige.^^

Es kann eine Weile dauern bis ich mich durch eure Links und Vorschläge gearbeitet hab. Meine eigene Idee zum Problem lege ich vorerst auf Eis. Mit etwas Glück bin ich in zwei oder drei Wochen wieder hier mit mehr oder weniger gut funktionierendem Code (C++) (auch wenn für so ein spezielles Problem nie jemand ausser mir einen Algorithmus bzw. Code brauchen wird. ).

Danke für eure Hilfe!