распознавание образов в матрице - PullRequest
4 голосов
/ 06 июля 2011

Я не уверен, что даю правильное имя этому, но в любом случае у меня есть матрица, которая по существу содержит 1 или 0. Матрица представляет собой квадратную матрицу, ее размеры могут быть 3х3, 4х4 или 5х5.

Под сопоставлением с образцом я подразумеваю найти некоторые «формы» в моей матрице, такие как линия, T или U, например ::1003* 0 1 0
0 1 0
1 1 1

эта матрица содержит T, но она также содержит 2 строки! Теперь, если матрица была 4х4, фигуры не увеличиваются, но они могут быть расположены в большем месте, например 0 0 0 0
1 1 1 0
0 0 1 0
1 1 1 0

Эта матрица будет содержать U (хотя строк нет, за исключением того, что строки имеют размер матрицы).

Наивно, так как матрица довольно мала, я бы попробовал все возможности для каждой фигуры, которую я хотел бы поддержать, но это не очень весело. Хотя я не могу придумать никакого алгоритма для этого, и неспособность правильно обозначить эту операцию не помогает;)

Кто-нибудь знает, как сделать это "эффективно"? (по сути, это может быть немного преувеличением, учитывая размер матрицы, но вы понимаете, о чем я).

Ответы [ 2 ]

0 голосов
/ 07 июля 2011

Я думал, что мог бы внести свой вклад в то, что я сделал, вот так, следуя идее aardvarkk.(код target-c) Я не был очень педантичен с проверками размера массива, потому что моя матрица - обязательно квадратная матрица.Также извините, если код некрасив: D

Я сделал небольшую структуру классов для фигур, которые я хочу преобразовать, у них есть список "направлений", которые по сути являются значениями перечисления.

-(BOOL)findShape:(NSInteger)size directions:(NSArray*)directions{
    NSMutableArray* current = [mgs tokens];
    for (int rot = 0; rot < 4; rot++) {
        for (int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++){
                NSInteger value = [[[current objectAtIndex:i] objectAtIndex:j] integerValue];
                if(value){
                    BOOL carryOn = [self iterateThroughDirections:directions i:i j:j tokens:current size:size];
                    if(carryOn){
                        return YES;
                    }
                }
            }
        }
        current = [self rotate:current];
    }
    return NO;
}


-(BOOL) iterateThroughDirections:(NSArray*)directions i:(NSInteger)i j:(NSInteger)j tokens:(NSMutableArray*)tokens size:(NSInteger)size{
    BOOL carryOn = YES;
    for(int k = 0; k < [directions count] && carryOn; k++){
        NSNumber* dir = [directions objectAtIndex:k];
        NSInteger d = [dir integerValue];
        //move in the direction
        switch (d) {
            case UP:
                if(i > 0){
                    i--;
                }else{
                    carryOn = NO;
                }
                break;
            case DOWN:
                if(i < size-1){
                    i++;
                }else{
                    carryOn = NO;
                }
                break;
            case LEFT:
                if(j > 0){
                    j--;
                }else{
                    carryOn = NO;
                }
                break;
            case RIGHT:
                if(j < size-1){
                    j++;
                }else{
                    carryOn = NO;
                }
                break;
            default:
                NSAssert(NO, @"invalid direction");
                break;
        }
        NSInteger v = [[[tokens objectAtIndex:i] objectAtIndex:j] integerValue];
        //now that we moved, check if the token is active, if it's not we're done
        if(!v){
            carryOn = NO;
            break;
        }
    }
    return carryOn;
}

-(NSMutableArray*)rotate:(NSMutableArray*)matrix{
    NSInteger w = [matrix count];
    NSInteger h = [[matrix objectAtIndex:0] count];
    NSMutableArray* rotated = [[NSMutableArray arrayWithCapacity:h] retain];
    for (int i = 0; i < h; i++) {
        [rotated addObject:[NSMutableArray arrayWithCapacity:w]];
    }
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            [[rotated objectAtIndex:i] addObject:[[matrix objectAtIndex:j] objectAtIndex:h-i-1]];
        }
    }

    return rotated;
}

Мне кажется, это хорошо работает!Еще раз спасибо за помощь!

0 голосов
/ 06 июля 2011

В вашем вопросе есть некоторая неопределенность. Например, делает:

1 1 1
1 1 1
1 1 1

содержит 6 строк, T, U и кучу других букв алфавита? Или все буквы разделены? Ваш первоначальный вопрос подразумевал, что буквы могут быть обнаружены перекрывающимся способом, потому что шаблон T содержит две строки. Таким образом, матрица, в которой все элементы были включены, будет содержать каждую возможную букву / строку в каждой возможной позиции.

Кроме того, я предполагаю, что вас беспокоит только поворот на 90 градусов, и вы не захотите пытаться найти смещенные на 45 градусов буквы, когда размеры матриц становятся достаточно большими, чтобы их поддерживать.

С точки зрения простоты реализации, подход грубой силы, о котором вы говорите (проверка каждой позиции на все четыре вращения букв), действительно выигрывает, я бы сказал.

В качестве альтернативы, вы можете получить довольно причудливое выражение (предупреждение: впереди смутные описания алгоритмов!):

1) Прогуливаясь по элементам матрицы, пока не найдете 1. Затем, по существу, заполните заливку из этой 1 в стеке и следите за изменениями направления. Затем используйте какой-нибудь инвариантный при вращении поиск, который отображал набор включенных пикселей на найденные буквы.

2) Используйте какое-либо описание целочисленного изображения или коробочного фильтра, чтобы взять суммы подразделов матрицы. Затем можно выполнить поиск по подразделам и сопоставить суммы подразделов со значениями букв / строк.

3) Поскольку комментарии определили, что вы действительно ищете только 4 фигуры, новый подход может оказаться полезным. Вы только исследуете 4 фигуры (линия, крест, T и U), если я не ошибаюсь. Каждый из них может быть в 4-х направлениях. Один быстрый совет: вы можете просто запустить алгоритм 4 раза, но повернуть основную матрицу на 90 градусов. Тогда вам не нужно настраивать вращение в вашем алгоритме. Также обратите внимание, что крест нужно найти только в одной ориентации, потому что он выглядит одинаково во всех четырех ориентациях, а линия идентична в двух ориентациях. В любом случае, вы могли бы сэкономить некоторую работу, отыскивая «самые сложные» вещи, которые должны соответствовать первым. Допустим, я ищу вертикальное «U» здесь:

1 0 1
1 0 1 
1 1 1

Я начинаю сверху слева. Вместо того, чтобы проверять, чтобы убедиться, что все пиксели «выключены» (или 0), я перехожу к следующему месту, где я ожидаю найти значение «вкл» (или 1). Допустим, это пиксель внизу слева вверху. Я проверяю средний левый пиксель, и он действительно включен. Затем я проверяю ниже этого. Если вы разрабатываете простой набор правил для каждой буквы, вы можете быстро отказаться от его поиска, если у вас не включены требуемые значения. Если вы затем запустите один и тот же алгоритм 4 раза и будете искать только вертикальные значения, я не уверен, что вы сможете добиться гораздо большего, чем этот!

Подходы, которые я упомянул, - просто идеи. Тем не менее, они могут доставить больше хлопот, чем стоят, с точки зрения повышения эффективности. И кто знает, они могут вообще не работать!

Удачи!

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...