Найти изображение шаблона (двоичный файл)

Question

Для строковой переменной в DigitalMicrograph мы можем найти положение определенного шаблона, используя функцию "найти":

Number find( String str, String sub_str )

Я хотел бы сделать то же самое, но с данными изображения. Например, я могу создать изображение с

image img := exprsize(1024, icol);

и шаблон, который я хочу найти,

image pattern := exprsize( 15, icol+64 );

В вышеприведенном случае мы знаем смещение шаблона относительно данных в столбце № 64. В реальном случае у нас не будет такого простого шаблона (то есть прямой линии). Подход с применением жесткой силы с помощью цикла for, безусловно, сработает, но он становится мучительно медленным, когда размер данных увеличивается. У кого-нибудь есть лучшее / элегантное предложение? 1D изображение может быть проще, как насчет 2D изображения?

Большое спасибо!

Answer 1

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

"Идея", которую я вложил в это: просто ищите вхождения последнего значения вашего шаблона поиска в потоке. Только если найдено, посмотрите, будет ли совпадать и начальное значение на данном расстоянии. Только в этом случае проверьте весь шаблон. Это должен быть полезный метод для длинных шаблонов поиска, но он не может быть настолько оптимальным для очень коротких.

{
    number patternSize = 8
    number dataSize = 24000
    number patternPos = trunc( random() * ( dataSize - patternSize ) )

    number const = 200
    number dataTypeSizeByte  = 4
    number stream_byte_order = 0

    // Prepare test-Dummies
        image searchSet := IntegerImage( "search", dataTypeSizeByte, 0, patternSize )
        searchSet = const * sin( icol/iwidth *  Pi() )
        // searchSet.ShowImage()

        image dataSet := IntegerImage( "data", dataTypeSizeByte, 0, dataSize ) 
        dataSet = const * random() * 0.3
        dataSet.Slice1( patternPos, 0, 0, 0, patternSize, 1 ) = searchSet
        // dataSet.ShowImage()

    // Prepare Data as RawStream
        object buffer = NewMemoryBuffer( dataSize * dataTypeSizeByte )
        object stream = NewStreamFromBuffer(buffer)
        dataSet.ImageWriteImageDataToStream( stream, stream_byte_order )
        stream.StreamSetPos(0,0)

    // Prepare aux. Tags for streaming
        TagGroup tg = NewTagGroup();
        tg.TagGroupSetTagAsUInt32( "UInt32_0", 0 )

    // Prepare values to search for 
        number startValue = searchSet.GetPixel(0,0)
        number lastValue =  searchSet.GetPixel(patternSize-1,0)

    // search for the pattern
        // Search for the LAST value of the pattern only.
        // If found, check if the FIRST value in appropriated distance also matches
        // Only then compare whole pattern.

        number value
        number streamEndPos = stream.StreamGetSize() 
        number streamPos = (patternSize-1) * dataTypeSizeByte // we can skip the first few tests
        stream.StreamSetPos(0, streamPos )  
        while( streamPos < streamEndPos )
        {
            tg.TagGroupReadTagDataFromStream( "UInt32_0", stream, stream_byte_order )
            streamPos = stream.StreamGetPos()

            tg.TagGroupGetTagAsUInt32( "UInt32_0", value )  // use appropriate data type!
            if ( lastValue == value )
            {
                result("\n Pattern might end at: "+streamPos/dataTypeSizeByte)

                // shift to start-value (relative) to check first value!
                stream.StreamSetPos(1, -1 * patternSize * dataTypeSizeByte )    
                tg.TagGroupReadTagDataFromStream( "UInt32_0", stream, stream_byte_order )
                tg.TagGroupGetTagAsUInt32( "UInt32_0", value )  
                if ( startValue == value )
                {
                    result("\t (Start also fits!) " )

                    // Now check all of it!
                    stream.StreamSetPos(1, -1 * dataTypeSizeByte )  
                    image compTemp := IntegerImage( "SectionData", dataTypeSizeByte, 0, patternSize )
                    compTemp.ImageReadImageDataFromStream( stream, stream_byte_order )

                    if ( 0 == sum( abs(compTemp - searchSet) ) )
                    {
                        number foundPos = (stream.StreamGetPos()/dataTypeSizeByte - patternSize)
                        Result("\n Correct starting position: " + patternPos )
                        Result("\n Found starting position  : " + foundPos )
                        OKDialog( "Found subset at position : " + foundPos )
                        exit(0)
                    }       
                }
                stream.StreamSetPos(0, streamPos )  
            }   
    }
    OKDialog("Nothing found.")
}

Answer 2

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

Image sourceData := RealImage("Source data", 4, 4096);
sourceData = Random();

Image targetPattern := RealImage("Target pattern", 4, 15);
targetPattern = sourceData.Index(icol + 1733, 0);

Затем мы подготовим тщательно упорядоченный поисковый буфер с одним выражением изображения:

Number targetSize = targetPattern.ImageGetDimensionSize(0);
Number searchBufferW = sourceData.ImageGetDimensionSize(0) - targetSize;
Image searchBuffer := RealImage("Search buffer", 4, searchBufferW, targetSize);
searchBuffer = sourceData.Index(icol + irow, 0);

Это упорядочивает все потенциальные совпадающие подмножества исходных данных в вертикальных столбцах 2D-изображения. Наконец, мы выполняем небольшую математическую обработку изображения, чтобы найти соответствие целевому шаблону, если он существует:

searchBuffer = Abs(searchBuffer - targetPattern.Index(irow, 0));
Image projectionVector := targetPattern.ImageClone();
projectionVector = 1.0;
Image searchResult := projectionVector.MatrixMultiply(searchBuffer);

Number posX, posY;
Number wasFound = (searchResult.Min(posX, posY) == 0);
String resultMsg = (wasFound) ? "Pattern found at " + posX : "Pattern not found";
OKDialog(resultMsg);

Первая строка даст точный ноль в каждом пикселе столбца буфера поиска, который соответствует целевому шаблону. Вертикальное суммирование буфера поиска и использование функции Min() для поиска нуля ускоряет поиск совпадения.

Обратите внимание на использование MatrixMultiply() для быстрой проекции вертикальной суммы. Это будет работать только для исходных данных типа Real (4-байтовые числа с плавающей запятой). Однако существуют несколько более сложные подходы к быстрому проецированию данных, которые также дадут довольно быстрый результат для любого числового типа данных.

Несмотря на то что проиллюстрировано для одномерного шаблона в одномерном наборе данных, этот подход, вероятно, может быть расширен до одномерных и двухмерных шаблонов в двухмерных и трехмерных наборах данных с использованием многомерного поискового буфера и более сложного индексирования с использованием объектов ImageDataSlice, но это будет предмет для другого вопроса.

Answer 3

Как указал Майк, взаимная корреляция является хорошим способом поиска паттерна в присутствии шума. Тем не менее, это даже лучше (если не идеальный метод) искать в отсутствие шума! Это будет работать в 1D и 2D для сценариев. Увидеть ниже

number sx = 1024
number sy = 1024
number pw = 32
number ph = 32
number px = 100 // trunc( random()*(sx-pw) )
number py = 200 // trunc( random()*(sy-ph) )

image test := RealImage("Data",4,sx,sy)
test = random()
image pattern := test[py,px,py+ph,px+pw].ImageClone()
//test.showimage()
//pattern.showimage()
image patternSearch = test*0
patternSearch[0,0,ph,pw] = pattern
//patternSearch.ShowImage()

image corr := CrossCorrelate(test,patternSearch)
corr.ShowImage()
number mx,my,mv
mv = max(corr,mx,my)
mx -= trunc(sx/2)       // because we've placed the pattern in the 
my -= trunc(sy/2)       // top/left of the search-mask
Result("\n Pattern = " + px + " / " + py )
Result("\n max = " + mv + " at " + mx + "/" + my )

image found = test*0
found[my,mx,my+ph,mx+pw]=pattern
rgbImage overlay = RGB((test-found)*256,found*256,0)
overlay.ShowImage()

Если ваша проблема только одномерная и у вас очень большие данные, то альтернативный подход может дать вам более быстрое решение. Затем я бы предложил попробовать использовать потоковую передачу RAW-данных (с помощью команд потоковой передачи TagGroup) и использовать любую дополнительную информацию, необходимую для настройки поиска, то есть искать только начало шаблона в потоке, а затем проверять только при ударе. " так далее.

Здесь добавлены примечания для решения проблемы, связанной с поиском в 1D изображении. Если мы запустим следующие сценарии пару раз, то обнаружим, что не удается правильно найти шаблон примерно в 50% случаев.

number sx = 1024
number sy = 0
number pw = 16
number ph = 0
number px = trunc( random()*(sx-pw) )
number py = 0 // trunc( random()*(sy-ph) )

image test := RealImage("Data",4,sx );
test = random();
image patternSearch := exprsize( sx, icol<pw? test[icol+px, irow]: 0 );
// test.ShowImage();
// patternSearch.ShowImage();
patternSearch.SetName( "PatternSearch" );
//

image corr := CrossCorrelate(test,patternSearch)
// corr.ShowImage()
number mx,my,mv
mv = max(corr,mx,my)
mx -= trunc(sx/2)       // because we've placed the pattern in the 
my -= trunc(sy/2)       // top/left of the search-mask
if( mx <= 0 ) mx += sx;
Result("\n\n Pattern = " + px + " / " + py )
Result("\n max = " + mv + " at " + mx + "/" + my )