Вопрос по алгоритму скелетизации от TheFire'a & theShockwave

[0101]

Цитирую описание алгоритма (http://xain.hackerdom.ru/zine/online/issue0/Breaking%20Da%20CAPTCHA.html#defend)

Цитата:

Недолго думая, было принято решение о разработке своего алгоритма (skeletonLetter). Для каждого черного пикселя проверяется несколько условий, если они выполняются, то пиксель помечается, но еще не удаляется из изображения. Помеченный пиксель для соседей по-прежнему считается черным. После того как все пиксели обработаны, помеченные удаляются, и алгоритм запускается заново. Если после очередного прохода ни одного пикселя не было удалено, то алгоритм завершается. Пиксель помечается, если выполнены следующие три условия:
у него строго больше одного черного соседа (функция pointB)
есть три подряд идущих белых пикселя при обходе соседей по часовой срелке (функция point03)
удаление этого пикселя не нарушает связности (функция checkConsistency)
Если убрать первое условие, то, когда будет уже выделен скелет, алгоритм не прекратит работу и от каждого "конца" скелета (пардон!) шаг за шагом будут продолжать съедаться пиксели, в результате не останется ни одного черного пикселя (буквы типа "О" имеют иммунитет). Второе условие отвечает за то, что пиксель является граничным, а не внутренним. Под третьим условием понимается запрет удаления крестовин, например у букв "У", "Х".

Попытался реализовать этот алгоритм. Если следовать условию Помеченный пиксель для соседей по-прежнему считается черным, то удаляются в итоге нужные пиксели. Мне кажется TheFire & theShockwave предложили некачественный алгоритм. Прав ли я?

[Yuri Gendelman]

0101 в сообщении #314324 писал(а):

Попытался реализовать этот алгоритм. Если следовать условию Помеченный пиксель для соседей по-прежнему считается черным, то удаляются в итоге нужные пиксели. Мне кажется TheFire & theShockwave предложили некачественный алгоритм. Прав ли я?

Судить о качестве алгоритма я не берусь, но само по себе это условие вполне разумно: результат алгоритма не должен зависеть от порядка обхода пикселов.

[0101]

Значит, алгоритм может быть рабочий. Но тогда как проверять сохранение связности? Не могу понять, каким образом эту задачу решает функция checkConsistency. Вот все функции, упомянутые TheFire & theShockwave, на C#.

checkConsistency

      private bool checkConsistency(int [,] m){
         int [,] tmp=new int[3,3];
         int bi=-1,bj=-1;
         for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
               if((tmp[i,j]=m[i,j])==1 && (i!=1||j!=1) ){bi=i;bj=j;}
            }
         }
         tmp[1,1]=0;
         if(bi!=-1){
            Queue q=new Queue(16);
            q.Enqueue(bi);
            q.Enqueue(bj);
            int i,j;
            while(q.Count!=0) {
               i=System.Convert.ToInt32(q.Dequeue));
               j=System.Convert.ToInt32(q.Dequeue));
            
               tmp[i,j]=0;

               if((i!=0)&&(j!=0)&&(tmp[i-1,j-1]==1)) {
                  q.Enqueue(i-1);q.Enqueue(j-1);
               }
               if(i!=0&&tmp[i-1,j]==1) {
                  q.Enqueue(i-1);q.Enqueue(j);
               }
               if(i!=0&&j!=2&&tmp[i-1,j+1]==1) {
                  q.Enqueue(i-1);q.Enqueue(j+1);
               }
               if(j!=0&&tmp[i,j-1]==1) {
                  q.Enqueue(i);q.Enqueue(j-1);
               }
               if(j!=2&&tmp[i,j+1]==1) {
                  q.Enqueue(i);q.Enqueue(j+1);
               }
               if(i!=2&&j!=0&&tmp[i+1,j-1]==1) {
                  q.Enqueue(i+1);q.Enqueue(j-1);
               }
               if(i!=2&&tmp[i+1,j]==1) {
                  q.Enqueue(i+1);q.Enqueue(j);
               }
               if(i!=2&&j!=2&&tmp[i+1,j+1]==1) {
                  q.Enqueue(i+1);q.Enqueue(j+1);
               }            
            }
            bi=-1;bj=-1;
            for(i=0;i<3;i++){
               for(j=0;j<3;j++){
                  if(tmp[i,j]==1 && (i!=1||j!=1) ){bi=i;bj=j;}
               }
            }
            if(bi!=-1) return false;
            else return true;
         }else{
            return true;
         }
      }

skeletonLetter

      private void skeletonLetter(ref Bitmap bmp){
         int i=1,j=1,width=bmp.Width,height=bmp.Height;
         int [,]bitmap=new int[width+2,height+2];
         
         for(i=2;i<width;i++){
            for(j=2;j<height;j++){
               if(bmp.GetPixel(i-1,j-1).GetBrightness()==0) bitmap[i,j]=1;
               else bitmap[i,j]=0;
            }
         }               
         int [,]okr=new int[3,3];
         int []okrs=new int[10];
         bool flag=true;
         while(flag){
            flag=false;
            for(i=1;i<=width;i++){
               for(j=1;j<=height;j++){
                  if(bitmap[i,j]==1){
                     okr[0,0]=okrs[0]=bitmap[i-1,j-1];
                     okr[1,0]=okrs[1]=bitmap[i,j-1];
                     okr[2,0]=okrs[2]=bitmap[i+1,j-1];
                     okr[2,1]=okrs[3]=bitmap[i+1,j];
                     okr[2,2]=okrs[4]=bitmap[i+1,j+1];
                     okr[1,2]=okrs[5]=bitmap[i,j+1];
                     okr[0,2]=okrs[6]=bitmap[i-1,j+1];
                     okr[0,1]=okrs[7]=bitmap[i-1,j];
                     okrs[8]=okrs[0];
                     okrs[9]=okrs[1];

                     if(pointB(ref okrs)>1 && point03(okrs) && checkConsistency(okr)){
                        bitmap[i,j]=2;
                        //MessageBox.Show(i.ToString()+" "+j.ToString());
                     }
                  }
               }
            }
            for(i=1;i<=width;i++){
               for(j=1;j<=height;j++){
                  if(bitmap[i,j]==2){
                     bitmap[i,j]=0;
                     flag=true;
                  }
               }
            }
         
         }
      
         for(i=1;i<=width-1;i++) {
            for(j=1;j<=height-1;j++) {
               if(bitmap[i,j]==1) bmp.SetPixel(i-1,j-1,Color.Black);
               else bmp.SetPixel(i-1,j-1,Color.White);
            }
         }
      }

point03

         
      private bool point03(int []m){
         for(int i=0;i<8;i++){
            if(m[i]==0 && m[i+1]==0 && m[i+2]==0){
               return true;
            }
         }
         return false;
      }

pointB

         
      private int pointB(ref int [] m) {
         int sum=0;
         for(int i=0;i<8;i++){
            if(m[i]!=0) sum++;
         }
         return sum;
      }

[Xaositect]

0101 в сообщении #314585 писал(а):

Но тогда как проверять сохранение связности? Не могу понять, каким образом эту задачу решает функция checkConsistency.

Это же просто алгоритм заливки. Мы от точки идем по всем направлениям и получаем новые точки, записываем в очередь. От точек в очереди тоже идем по всем направлениям, получаем новые точки, записываем в очередь. В итоге мы обойдем все точки связной области, в которой содержится самая первая точка. Если больше точек нет - фигура связная.

[0101]

Если при перекраске данного пикселя связность черных из соседних 8-ми не нарушится , значит его можно пометить. Для соседей он остается черным. Если нужно перекрасить только один из 2-х пикселей, помечены и перекрашены будут оба. Я думал, вся хитрость метода в checkConsistency. Получается, смысл checkConsistency только в проверке связности 8-ми соседей данного пикселя, и ни в чем ином. В итоге реализуемость алгоритма TheFire & theShockwave остается под вопросом.