Собственно субж. Есть HBITMAP N1 и HBITMAP N2.

Как определить, содержится ли N2 в N2 и желательно получить его координаты(верхнюю левую точку)?

упс, вопрос — "N2 в N1" ?

Здравствуйте Аноним, Вы писали:

А>упс, вопрос — "N2 в N1" ?

Поиск вхождения должен быть точным или приблизительным (тоесть имеется полное совпадение пикселей или нет)?

Если нужно найти точно сопадающее вхождение, то самый простой вариант — делается GetDIBits для обоих картинок и делается последовательное сравнение картинок (поиск массива первой картинки в массиве второй картинки). Разумеется нужно учитывать размеры (геометрические) обоих картинок и использовать эти данные при поиске. Также необходимо учесть что картинки могут быть с индексироваными цветами (4, 8 BPP) тогда надо сравнивать не пиксели а их цвета в палитре.
Это все справедливо для случая, когда картинки имеют одинаковую глубину цвета и одна из них полностью идентична региону другой картинки, причем прямоугольному, а не произвольному.

Однако когда нет 100% вхождения, алгоритм поиска усложняется на порядки. Пример программы реализуещей такой подход — FineReader.

Здравствуйте IgorK, Вы писали:

IK>Поиск вхождения должен быть точным или приблизительным (тоесть имеется полное совпадение пикселей или нет)?

здесь всё правильно — нужно найти точное вхождение прямоугольника N2 в прямоугольник N1

IK>Если нужно найти точно сопадающее вхождение, то самый простой вариант — делается GetDIBits для обоих картинок и делается последовательное сравнение картинок (поиск массива первой картинки в массиве второй картинки). Разумеется нужно учитывать размеры (геометрические) обоих картинок и использовать эти данные при поиске. Также необходимо учесть что картинки могут быть с индексироваными цветами (4, 8 BPP) тогда надо сравнивать не пиксели а их цвета в палитре.

вот здесь мне очень интересно как учитывать геометрические параметры. Судя по MSDN, GetDIBits копирует участок с некой строчки битмапа Nx с количеством y строк. Но ведь второй битмап отличается не только по длине, но и по ширине! Получается, максимум чего мы добьёмся — это сузим поиск по вертикали. А как его дальше осуществлять по горизонтали ? :???:

Здравствуйте Аноним, Вы писали:

А>вот здесь мне очень интересно как учитывать геометрические параметры. Судя по MSDN, GetDIBits копирует участок с некой строчки битмапа Nx с количеством y строк. Но ведь второй битмап отличается не только по длине, но и по ширине! Получается, максимум чего мы добьёмся — это сузим поиск по вертикали. А как его дальше осуществлять по горизонтали ? :???:

Зачем заранее сужать поиск вообще? Этим можно отрезать часть искомого вхождения :)
Просто получаем полные массивы на обе картинки и начиная с первого пикселя ищем вхождение.

Пусть I (от image) — это большая картинка, а P (от part) — это кусочек, который мы ищем в большой картинке. Также нам известны размеры картинок (sxI, syI, sxP, syP). Зададимся еще счетчиками xI, yI, xP, yP. pI и pP — указатели на массивы большой и маленькой картинок соотвественно.

Алгоритм примерно такой (псевдокод, почти С++ :) ):

bool FindEntry(pI, sxI, syI, pP, sxP, syP, POINT* pt)
{
  for(yI = 0; yI < (syI - syP); yI++)
  {
    for(xI = 0; xI < (sxI - sxI); xI++)
    {
      if(isEntry(pI, sxI, xI, yI, pP, sxP, syP))
      {
        pt->x = xI; 
        pt->y = yI;
        return true;
      }
    }
  }

  return false;
}

bool isEntry(pI, sxI, xI, yI, pP, sxP, syP)
{
  for(yP = 0; yP < syP; yP++)
  {
    for(xP = 0; xP < sxP; xP++)
    {
       // самая главная строчка кода :)
       if( *(pI + xI + xP + (sxI * yI) + (sxI * yP)) != *(pP + xP + (sxP * yP) ) return false;
    }
  }

  return true;
}

Ну вот и все вроде-бы...

Здравствуйте IgorK, Вы писали:

IK>Зачем заранее сужать поиск вообще? Этим можно отрезать часть искомого вхождения :)
IK>Просто получаем полные массивы на обе картинки и начиная с первого пикселя ищем вхождение.
[skipped]
IK>Ну вот и все вроде-бы...

ага, спасибочки. Алгоритм понятен. В общем, попиксельное сравнивание в циклах. Получается GetDIBits даже и не надо использовать. :-\

Есть одна проблема в таком случае. Сложность такого алгоритма будет sxI*syI*sxP*syP. При скромных размерах картинки 500х500 и её маленькой части 100х100 мы получаем порядка 10^10 шагов. Боюсь я, что это будет не совсем быстро даже на современных компьютерах :-\

Хорошо бы было использовать какой-нибудь API или стандартную (вылизанную) функцию. Например, как приятно искать вхождение подстроки в строку ;-) — strstr() и ни о чём не заботишься....

Здравствуйте Аноним, Вы писали:


А>ага, спасибочки. Алгоритм понятен. В общем, попиксельное сравнивание в циклах. Получается GetDIBits даже и не надо использовать.

GetDIBits как раз вернет указатель на скопированный массив пикселей, это упрощает задачу.

А>Есть одна проблема в таком случае. Сложность такого алгоритма будет sxI*syI*sxP*syP. При скромных размерах картинки 500х500 и её маленькой части 100х100 мы получаем порядка 10^10 шагов. Боюсь я, что это будет не совсем быстро даже на современных компьютерах

При наихудшем стечении обстоятельств, алгоритм сделает (sxI-sxP)*(syI-syP)*sxP*syP итераций, но на самом деле все зависит от того, какая у тебя картинка. Да чего там говорить — это же проверить несложно. Ты реализуй — а потом нам раскажешь быстро это или нет

А>Хорошо бы было использовать какой-нибудь API или стандартную (вылизанную) функцию. Например, как приятно искать вхождение подстроки в строку — strstr() и ни о чём не заботишься....

стандартного, имхо, нету.

Здравствуйте Аноним

Ты бы зарегистрировался чтоль, а то с Анонимом как-то не комфортно общаться...

Ну вот например интеловский код (точнее, кусочек кода) для Motion Estimation (MPEG). Я когда-то читал на сайте Интела.
В даннном алгоритме выполняется поиск макроблока, "подобного" требуемому, т.е. используется функция ошибки.

int PLogarithmicSearch(uint8* currentBlock,uint8* prev,int by,int bx,int* motionY,int* motionX)
{
  int  bestdifc=0x7fffffff,difc; 
  int  bestdifm=0x7fffffff,difm; 
  int  bestdifmm=0x7fffffff,difmm; 
  int     upperMY, bottomMY;
  int     leftMX, rightMX;
  int     tempBottomMY, tempRightMX;
  int     spacing;
  int     centerX, centerY;
  int     newCenterX, newCenterY;
  int     newCenterXc, newCenterYc;
  int     newCenterXm, newCenterYm;
  int     newCenterXmm, newCenterYmm;
  int  mx, my;
  int  bestDiff = 0x7fffffff;

  spacing = (logsearchRange+1)/2;
  upperMY =0;
  leftMX  =0;
  bottomMY=FRAME_HEIGHT - BLOCK_SIZE;
  rightMX=FRAME_WIDTH - BLOCK_SIZE;
  centerX = bx;
  centerY = by;
  
 
  while ( spacing >= stepSize ) 
  {
      newCenterY = centerY;
      newCenterX = centerX;
 
      tempBottomMY = bottomMY;
      if ( centerY+spacing+1 < tempBottomMY ) 
    {
        tempBottomMY = centerY+spacing+1;
    }
      tempRightMX = rightMX;
      if ( centerX+spacing+1 < tempRightMX ) 
    {
        tempRightMX = centerX+spacing+1;
      }

     
      for ( my = centerY-spacing; my < tempBottomMY; my += spacing ) 
    {
        if ( my < upperMY ) 
      {
            continue;
        }

        for ( mx = centerX-spacing; mx < tempRightMX; mx += spacing ) 
      {
              if ( mx < leftMX ) 
        {
                  continue;
              }
              
          difmm= MotionErrorXMM(prev,currentBlock,mx,my,bestdifmm);
          
                      
#ifdef C_MMX
      
              difc= MotionErrorC(prev,currentBlock,mx,my,bestdifc);
              difm= MotionErrorMMX(prev,currentBlock,mx,my,bestdifm);

           
            if(difc < bestdifc)
            {
          newCenterYc = my;
          newCenterXc = mx;
              bestdifc=difc;
            }

        if(difm < bestdifm)
            {
          newCenterYm = my;
              newCenterXm = mx;
              bestdifm=difm;
            }
#endif
  
        if(difmm < bestdifmm)
        {
          newCenterYmm = my;       
          newCenterXmm = mx;
          bestdifmm=difmm;
        }  

#ifdef C_MMX
        if((bestdifc!=bestdifm)||(bestdifc != bestdifmm)||(bestdifm != bestdifmm))
        {
          fprintf(stderr, " EstBlock(%d,%d),refblock(%d,%d): bestdifc=%d,bestdifm=%d,
                  bestdifmm=%d \n",by,bx,my,mx,bestdifc,bestdifm,bestdifmm);
          exit(1);
        }     
        if((newCenterXc!=newCenterXm)||(newCenterXc!=newCenterXmm)||
           (newCenterYc!= newCenterYm)||(newCenterYc!= newCenterYmm))
        {
          fprintf(stderr, "EstBlock(%d,%d),refblock(%d,%d):newCenterXc=%d,newCenterYc=%d,newCenterXm=%d,
          newCenterYm=%d,newCenterXmm=%d,newCenterYmm=%d \n",
          by,bx,my,mx,newCenterXc,
          newCenterYc,newCenterXm,newCenterYm,newCenterXmm,newCenterYmm);
          exit(1);
        }    
      
#endif      
          newCenterY = newCenterYmm;
        newCenterX = newCenterXmm;
        bestDiff = bestdifmm;
      }
       
    }

      //moving center to best match block location
      centerY = newCenterY;
      centerX = newCenterX;

      // update the spacing  
    if ( spacing == 1 ) 
    {
        spacing = 0;
      } 
    else 
    {
        spacing = (spacing+1)/2;
      }
  }//while


  *motionY = centerY;
  *motionX = centerX;

  return bestDiff;
}

Здравствуйте IgorK, Вы писали:

IK>Здравствуйте Аноним

IK>Ты бы зарегистрировался чтоль, а то с Анонимом как-то не комфортно общаться...

вот и я !

просто что-то с первого раза процедура регистрации не прошла. то ли инет у меня плохой, то ли я тормоз

Здравствуйте IgorK, Вы писали:

IK>При наихудшем стечении обстоятельств, алгоритм сделает (sxI-sxP)*(syI-syP)*sxP*syP итераций, но на самом деле все зависит от того, какая у тебя картинка. Да чего там говорить — это же проверить несложно. Ты реализуй — а потом нам раскажешь быстро это или нет

короче чего-то я накропал, вот только одна проблема — оно не работает

зря волновался, ищет достаточно быстро — при размерах картинок 640*480 и 80*80 соответственно успевает обработать где-то за 50мс. Правда думаю, что так как вхождение не находится, алгоритм лажается еще на первой строке маленького изображения.

вот собственно код на основе твоего псевдокода с исправленными неточностями :

bool isEntry(LPSTR pI, DWORD sxI, DWORD syI, LPSTR pP, DWORD sxP, DWORD syP, DWORD xI, DWORD yI )
{
  for(DWORD yP = 0; yP < syP; yP++)
  {
    for(DWORD xP = 0; xP < sxP; xP++)
    {
       // самая главная строчка :)) 
       if( *(pI + xI + xP + (sxI * yI) + (sxI * yP)) != *(pP + xP + (sxP * yP) ) )
       {
           return false;
       }
    }
  }
  return true;
}

bool FindEntry(LPSTR pI, DWORD sxI, DWORD syI, LPSTR pP, DWORD sxP, DWORD syP, POINT* pt)
{
  for(DWORD yI = 0; yI < (syI - syP); yI++)
  {
    for(DWORD xI = 0; xI < (sxI - sxP); xI++)
    {
      if( isEntry(pI, sxI, syI, pP, sxP, syP, xI, yI) )
      {
        pt->x = xI; 
        pt->y = yI;
        return true;
      }
    }
  }
  return false;
}

ну и вызывается это всё примерно так:

    POINT ptEntry = {0,0};
    if( true == FindEntry( lpImgDIBBits, DIBHeight(lpImgDIBHdr), DIBWidth(lpImgDIBHdr), 
                           lpPartDIBBits,DIBHeight(lpPartDIBHdr), DIBWidth(lpPartDIBHdr), 
                           &ptEntry ) )
    {
        printf("found with coordinates: (%d,%d)\n", ptEntry.x, ptEntry.y);
    }

Функции для работы с DIB взяты из чудного примера WINCAP.

Еще раз повторюсь — одна осталась проблема — ничего не находится. Даже на самом простом примере где и первая и вторая картинки просто одноцветная заливка, оно вторую не находит Битмапы цветные 24b. Нутром чувствую, где-то баг Но где ?

Здравствуйте visitant, Вы писали:

V>Ну вот например интеловский код (точнее, кусочек кода) для Motion Estimation (MPEG). Я когда-то читал на сайте Интела.
V>В даннном алгоритме выполняется поиск макроблока, "подобного" требуемому, т.е. используется функция ошибки.

ой, как-то там всё сложно мне-бы чего попроще, а если сложное то чтобы сразу работало только подставь туда параметры да еще и знать какие

может ты хотя бы обьяснишь простым языком чего там происходит в этой процедуре ?

Ну вот, почитай, что происходит в этой процедуре.
Using Streaming SIMD Extensions in a Motion Estimation Algorithm for MPEG Encoding

SS> Нутром чувствую, где-то баг ;) Но где ? :???:

когда цикл в isEntry переходит на вторую строчку, то есть yP == 1, то вся синхронихация массива почему-то теряется — может +1 или -1 байт надо сдвигать ? тогда почему ?

Или вот какая идея — может в битмапе информация разверткой по вертикали а не по горизонтали ? :???: