Muster in Array suchen

[iTutHD]

Hallo,
Ich habe folgendes Problem:
ich habe ein 2D Array a und ein 2D Array b, nun möchte ich schauen ob es eine stelle gibt(und wenn ja wo) das Array b in seiner Form im Array a vorkommt. Dabei muss aber auch die Postion aber übereinstimmen also z.B.
a =
xyxy
yyyy
xxcc

b =
y
xc

Dann ist die einzige lösung a[2][3] und a[3][3] und a [3][4]. Ich hoffe das ist irgend wie verständlich.
Nun habe ich folgenden Code:

        int k = 0;
        int pos_i = 0;
        int pos_j_min = 0;
        int pos_j_max = 0;
       
        for(int i = 0; i < a.length; i++){
            for(int j = 0; j < a[i].length; j++){
                    if(k < b[0].length && a[i][j] == b[0][k]){
                        if(pos_j_min == 0){
                            pos_j_min = j;
                            pos_i = i;
                        }
                        else if(j - pos_j_min == b[0].length){
                            pos_j_max = j;
                        }
                    }
                       
            }//y von a
        }// x von a
        if(pos_j_max - pos_j_min == b[0].length){
            System.out.println(pos_j_min + " " + pos_j_max);
        }
        else{
            System.out.println("error" + pos_j_min + " " + pos_j_max);
        }

Leider sucht der mir ja nur erstmal für b[0][length] das richtige und das wäre ja schon bei a[0][1] gegeben.
Kann mir wer helfen das zu erweitern bzw. erklären wie das lösbar wäre?

 

[neoexpert]

public class Main
{

    public static void main(String[] args)
    {
        char[][] a = {
            {'0', '1', '2', '3'},
            {'4', '5', '6', '7'},
            {'8', '9', 'a', 'b'},
            {'c' ,'d' ,'e' ,'f'}};
        char[][] b = {
            {'5', '6'},
            {'9', 'a'}};
        if(new Main().contains(a,b))
            System.out.println("c");
    }
    boolean contains(char[][] a, char[][] b){
        for (int y=0;y < a.length-b.length;y++)
        {
            for (int x=0;x < a[y].length-b[y].length;x++)
            {
                if(check(a,b,x,y))
                    return true;
            }
        }
        return false;
    }
    boolean check(char[][] a, char[][] b,int dx,int dy){
        for (int y=0;y < b.length;y++)
        {
            for (int x=0;x < b[y].length;x++)
            {
                if(a[x+dx][y+dy]!=b[x][y])
                    return false;
            }
        }
        return true;
    }
}

Interessant, du kannst damit in Bildern nach Mustern suchen. Es gibt sicherlich Varianten die schneller funktioieren. Irgendwie funktionieren ja die Gesichtsscanner.
EDIT:
Achso: man könnte ja die Bilder gröber machen und die Suche weicher also die Farben des Pixels auf Ähnlichkeit prüfen. Echt cool.
Faszinierend

 

[Thallius]

Also bei mir hat dein Beispiel Array A überhaupt kein a[3][3] und a[3][4]....

 

[neoexpert]

Also bei mir hat dein Beispiel Array A überhaupt kein a[3][3] und a[3][4]....

Mein Beispiel? Ich habe eben auf die schnelle was hingeschrieben, habe nicht ausreichend getestet.

 

[neoexpert]

Korrektur:

public class Main
{

    public static void main(String[] args)
    {
        char[][] a = {
            {'0', '1', '2', '3'},
            {'4' ,'5', '6', '7'},
            {'8', '9', 'a', 'b'},
            {'c', 'd', 'e', 'f'}};
        char[][] b = {
            {'a', 'b'},
            {'e', 'f'}};

         if (new Main().contains(a, b))
            System.out.println("c");
    }
    boolean contains(char[][] a, char[][] b)
    {
        for (int y=0;y < a.length;y++)
        {
            for (int x=0;x < a[y].length;x++)
            {
                if (check(a, b, x, y))
                    return true;
            }
        }
        return false;
    }
    boolean check(char[][] a, char[][] b, int dx, int dy)
    {
        for (int y=0;y < b.length;y++)
        {
            for (int x=0;x < b[y].length;x++)
            {
                if (a[x + dx][y + dy] != b[x][y])
                    return false;
            }
        }
        return true;
    }
}

 

[neoexpert]

Hier noch eine Variante:
Da kannst du beliebige Arraylängen verwenden. Das zeichen * ist dabei Platzhalter für beliebiges zeichen:

public class Main
{

    public static void main(String[] args)
    {
        char[][] a = {
            {'0', '1', '2', '3'}, 
            {'4' ,'5', '6', '7'}, 
            {'8', '9', 'a', 'b'},
            {'c', 'd', 'e', 'f'}};
        char[][] b = {
            {'5', '*'}, 
            {'9', 'a'}};

        if (new Main().contains(a, b))
            System.out.println("c");
    }
    boolean contains(char[][] a, char[][] b)
    {
        for (int y=0;y < a.length;y++)
        {
            for (int x=0;x < a[y].length;x++)
            {
                if (check(a, b, x, y))
                    return true;
            }
        }
        return false;
    }
    boolean check(char[][] a, char[][] b, int dx, int dy)
    {
        for (int y=0;y < b.length;y++)
        {
            for (int x=0;x < b[y].length;x++)
            {
                if(b[y][x]=='*')
                    continue;
                if(y + dy>=a.length||x + dx>=a[y + dy].length)
                    continue;
                if (a[y + dy][x + dx] != b[y][x])
                    return false;
            }
        }
        return true;
    }
}

 

[Naryxus]

Hey,

interessantes Thema!

Im Vergleich zu neoexpert verfolge ich bei mir einen rekursiven Ansatz. Ich habe auch gleich mal das Speichern der Positionen mit eingebaut, wobei das wahrscheinlich auch in neoexperts Lösung einfach möglich wäre.
Um zu sagen, welche Lösung jetzt effizienter ist, müsste ich mir die beiden Algorithmen genauer anschauen. Aber oft wählt man eine Lösung ja schon, ob man mehr auf Rekursionen oder Iterationen steht. Ich fand in diesem Fall Rekursionen recht ansprechend.

Zuerst einmal würde ich auf folgende Fälle testen (und ausschließen): Der Algorithmus macht nur Sinn, wenn die Dimensionen des einen Arrays größer gleich der Dimensionen des anderen Arrays ist. Das heißt ein Array mit den Dimensionen 2x3 kann niemals ein Teil eines Arrays mit den Dimensionen 3x2 sein.
Dies definiert eine Ordnungsrelation der Arraydimensionen.

Ich habe zuerst das Problem auf das zeilenweise Suchen eingeschränkt:

static Set<Integer> checkRow(int start, char[] row, char[] patternRow) {
   if(start > row.length - patternRow.length)
      return new HashSet<>();
   Set<Integer> out = Checker.checkRow(start + 1, row, patternRow);
   boolean check = true;
   for(int col = 0; col < patternRow.length; col++) {
      if(patternRow[col] != '\0' && row[start + col] != patternRow[col]) {
         check = false;
         break;
      }
   }
   if(check)
      out.add(start);
   return out;
}

Damit werden schon einmal alle Positionen in der Zeile ausgegeben, an denen die Zeile mit der Musterzeile übereinstimmt. Das ganze muss natürlich auch rekursiv sein, da das Muster potenziell an jedem Zeichen der Zeile beginnen kann.

Jetzt muss das ganze noch zweidimensional erweitert werden und sieht ganz ähnlich aus:

static Set<Point> check(int start, char[][] a, char[][] b) {
   if(start > a.length - b.length)
      return new HashSet<>();
   Set<Point> out = Checker.check(start + 1, a, b);
   Set<Integer> cols = IntStream.range(0, a[start].length).boxed().collect(Collectors.toSet()); //(0, 1, 2, ..., a[start].length - 1)
   int row = 0;
   do {
      cols.retainAll(Checker.checkRow(0, a[row], b[row])); //Schnittmenge der Startindizes der Zeilen
      row++;
   } while(row < b.length && !cols.isEmpty());
   cols.forEach(col -> out.add(new Point(start, col)));
   return out;
}

Das Grundprinzip hier: Man berechnet zeilenweise die Startindizes der Zeilen bezüglich des Musters und bildet dann die Schnittmenge. Der Gedanke dahinter ist, dass wenn in Zeile 1 des Testarrays die Zeile 1 des Musters ab Position 3 zu finden ist, muss auch Zeile 2 des Musters ab Position 3 in der Zeile 2 des Testarrays zu finden sein.
Und auch hier natürlich wieder rekursiv, da das Muster auch in Zeile i starten kann.

Mein Test mit den Arrays
char[][] test = {{'a', 'b', 'a', 'b'},
{'b', 'a', 'b', 'a'},
{'a', 'b', 'a', 'b'}};
char[][] pattern = {{'a', 'b'},
{'b', 'a'}};

liefert die korrekten Positionen [java.awt.Point[x=1,y=0], java.awt.Point[x=1,y=2], java.awt.Point[x=0,y=0], java.awt.Point[x=0,y=2]].

Ich hoffe, ich konnte dir etwas helfen.

Grüße Naryxus

 

[neoexpert]

Bei Rekursionen kann es zu Stack-Überlauf kommen. Aber man kann jede Rekursion in eine Iteration transformieren.

 

[Naryxus]

Ja, da hast du Recht. Natürlich muss man da schauen, in welchen Größenordnungen man arbeitet.

Wie ich schon gesagt habe, bleibt es dann eine "Sympathieentscheidung", ob man eine Rekursion oder Iteration verwendet, falls man sich um Überläufe keine Sorgen machen muss.

 

[neoexpert]

Ich würde jetzt diesen Algorithmus verwenden um nach Mustern in Bildern zu suchen. Erstmal die Bilder grob durchsuchen (niedrige Auflösung) und dann falls verschwommenes Gesicht gefunden wird, etwas genauer in dies Bereich nach Gesichtstrukturen suchen. Meinst du das kann Funktionieren?

 

[Naryxus]

Meinst du jetzt bezüglich Rekursion/Iteration? Wenn ja kommt das auf verschiedene Faktoren an. Wie groß du die Bilder betrachtest und wie leistungsfähig dein System ist.

Wenn du vom Prinzip her fragst: Ich denke, dass es eine gute Grundlage für eine Mustererkennung ist. Das Problem wird jedoch die unterschiedliche Skalierung sein. So wie der Algorithmus ist, kann er erstmal nur das Muster in einer einzigen Größe "erkennen". Nämlich in der, in der er als Array gespeichert ist. Es gibt einige Algorithmen, die dann noch das Testbild in einer Anzahl an Iterationen um einen gewissen Faktor größer/kleiner skaliert und dann jeweils testet, ob das Muster erkannt wird.

Ein weiteres Problem wird in jedem Fall die "Ähnlichkeitsrelation" in einem Bild sein. Also die Entscheidung bis zu welchem Grad das Testbild das Muster toleriert (Muss das Pixel wirklich komplett weiß sein oder reicht auch ein heller Grauton?)

Die Frage ist auch letztendlich immer, was du für ein Muster erkennen möchtest. Geht es wirklich um die Identifikation von Elementen in einem Bild, wird solch ein Algorithmus wahrscheinlich grundlegend sein.
Ich habe mal an einer Gestenerkennung gearbeitet. Dort hat der Benutzer mit der Maus eine geometrische Figur gezeichnet und das Programm hat die Form automatisiert erkannt. Hier habe ich dann mit einer Folge von Richtungsvektoren gearbeitet, um die Winkelsumme der gezeichneten Form zu erkennen und als Feature für ein neuronales Netz zum maschinellen Lernen verwendet.

Was ich damit sagen möchte, ist, dass verschiedene Algorithmen auch mit unterschiedlichen Featuren arbeiten können. Auch wenn der Ursprungsinput ein Bild ist.
Ich könnte mir zum Beispiel auch vorstellen, dass du einen Clustering-Algorithmus über das Bild laufen lässt, um ähnliche Bereiche zu finden.