Алгоритм поиска прямоугольников в bmp

[Pcrepair]

Добрый день. Есть задача поиска прямоугольников в BMP файле со следующими параметрами:
1) исходный файл черно-белый (белый цвет значащий), разрядность 1-бит
2) размер файла 1920х1031 пиксель, но это не принципиально, размеры могут быть всякие
3) фигуры внутри файла могут быть всякие, но это не принципиально, нужны только прямоугольники, даже если сложная фигура будет определена как прямоугольник значения не имеет

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

procedure TMain.Button1Click(Sender: TObject);
var
  rLeft, rTop, rRigth, rBottom, rMinH, rMinW: Integer;
  glBitMap: Vcl.Graphics.TBitmap;
  rRestsList: string;
begin  // запуск процесса поиска
  glBitMap := TBitmap.Create;
  try
    if FindRects(glBitMap, rRestsList) then
      Memo1.Lines.Add(rRestsList);
  finally
    FreeAndNil(glBitMap);
  end;
end;

(* 2024.12.21 to find all exseptable rectigies coordinates in bmp *)
function FindRects(const aBitmap: Vcl.Graphics.TBitmap; var aRestsList: string): Boolean;
var
  H, W, hStart, wStart: Integer;
  stFlg: Boolean;
  Clr, aLeft, aTop, aRigth, aBottom: Integer;
  RestsList: string;
begin
  Result := false;
  hStart := 0;  // установка поиска в начало координат файл.БМП
  wStart := 0;

  repeat // повтор поиска
    stFlg := false;
	
    // функция DefineRectCoo возвращает ДА и координаты лево-верх-справа-низ ПЕРВОГО! найденного прямоугольника в файл.БМП
    if DefineRectCoo(aBitmap, hStart, wStart, aLeft, aTop, aRigth, aBottom) then  
    begin
      (* send data to output *)  //сбор координат найденных прямоугольников
      Insert((IntToStr(aLeft) + ':' + IntToStr(aTop) + ':' + IntToStr(aRigth) + ':' + IntToStr(aBottom) +
        sLineBreak), aRestsList, (aRestsList.Length + 1));
      (* ---------------------- *)

      stFlg := true; //запуск повторного поиска
    end;

    (* next rigth-top rect *)
    hStart := aTop; wStart := aRigth + 1;  //поиск из новой начальной точки: верх-справа от найденного прямоугольника

  until (stFlg = false);

  if (aRestsList.Length > 0) then
    Result := true;
end;
(* -------------------------------------------- *)

все почти хорошо, но определяюттся только координаты всех прямоугольников которые справа от найденного (hStart := aTop; wStart := aRigth + 1, никак не придумаю алгоритм для поиска всех прямоугольников
file.bmp входной файл
data.bmp результат поиска

вопрос: может кто что подскажет по алгоритму?

Заранее спасибо за ответы по ЗАДАННЫМ вопросам

[DeepFlake]

Изображение разбивается на два изображения посередине горизонтальной линией. Делается поиск в верхнем и в нижнем изображении. Потом каждое изображение ещё разбивается напополам и т.д. Вобщем рекурсивный поиск.

[DeepFlake]

Предлагаю такой алгоритм:
изображение покрывается сеткой из точек, расстояние по вертикали и горизонтали между точками - половина от минимального размера прямоуголника.
Далее проходим по каждой точке, если она попала в прямоуголник (то есть соответствующий цвет), то идём от этой точки влево, вправо, вверх, вниз то тех пор, пока не изменится цвет (то есть пока не закончится прямоуголник). Таким образом мы можем определить координаты прямоуголника. Эти координаты добавляем в список, а последующие точки проверяем на вхождение в прямоугольник в списке. Если точка входит в уже найденный прямоугольник, то переходим к следующей точке.
В реальной программе надо предварительно изображение обработать для исключения шума.
Вот программа на Java, демонстрирущая основной алгоритм:

// License: Public domain.

public class rect_recogn
{
    public static
        void main( final String args[] )
    {
        final int       img_rows = 15;
        final int       img_cols = 12;
        final byte [][] img = {
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, 0, 0, 0, 0, 0, 0 },
            { 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, 0, 0, 0, 0, 0, 0 },
            { 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, 0, 0, 0, 0, 0, 0 },
            { 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, 0, 0, 0, 0, 0, 0 },
            { 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
            { 0, 0, 0, 0, 0, 0, 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF },
            { 0, 0, 0, 0, 0, 0, 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF },
            { 0, 0, 0, 0, 0, 0, 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF },
            { 0, 0, 0, 0, 0, 0, 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF },
            { 0, 0, 0, 0, 0, 0, 0, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF, (byte)0xFF }
        };
        
        final int       rect_min_size = 5;
            // минимальная ширина или высота прямоугольника
        
        final int       grid_step = (int) java.lang.Math.round( rect_min_size/2.0 );
            // расстояние между точками сетки по вертикали и горизонтали
        
        final byte      rect_color = (byte) 0xFF;
        
        java.lang.System.out.println( "Нахождение прямоуголников в изображении." );

        for ( int row_ind = grid_step; row_ind < img_rows; row_ind += grid_step )
        {
            for ( int col_ind = grid_step; col_ind < img_cols; col_ind += grid_step )
            {
                java.lang.System.out.println( "row="+ row_ind +" col="+ col_ind );
                if ( img[ row_ind] [ col_ind ] == rect_color )
                {
                    java.lang.System.out.println( "\tin rectangle" );
                    // идём влево от точки
                    int trip_point = col_ind;
                    while ( img[ row_ind ][ trip_point ] == rect_color )
                    {
                        --trip_point;
                        if ( trip_point <= 0 )
                        {
                            // достигли левого края изображения
                            break;
                        }
                    }
                    java.lang.System.out.println( "\tleft side is "+(trip_point+1) );

                    // идём вправо от точки
                    trip_point = col_ind;
                    while ( img[ row_ind ][ trip_point ] == rect_color )
                    {
                        ++trip_point;
                        if ( trip_point >= img_cols )
                        {
                            // достигли правого края изображения
                            break;
                        }
                    }
                    java.lang.System.out.println( "\tright side is "+(trip_point-1) );

                    // идём вверх от точки
                    trip_point = row_ind;
                    while ( img[ trip_point ][ col_ind ] == rect_color )
                    {
                        --trip_point;
                        if ( trip_point <= 0 )
                        {
                            // достигли верхнего края изображения
                            break;
                        }
                    }
                    java.lang.System.out.println( "\ttop side is "+(trip_point+1) );

                    // идём вниз от точки
                    trip_point = row_ind;
                    while ( img[ trip_point ][ col_ind ] == rect_color )
                    {
                        ++trip_point;
                        if ( trip_point >= img_rows )
                        {
                            // достигли нижнего края изображения
                            break;
                        }
                    }
                    java.lang.System.out.println( "\tbottom side is "+(trip_point-1) );

                    
                }
                
            }
        }
        


    }
}

Здесь изображение в виде массива, а в нём два прямоуголника.
Вот такой вывод у программы:

Нахождение прямоуголников в изображении.
row=3 col=3
	in rectangle
	left side is 1
	right side is 5
	top side is 1
	bottom side is 5
row=3 col=6
row=3 col=9
row=6 col=3
row=6 col=6
row=6 col=9
row=9 col=3
row=9 col=6
row=9 col=9
row=12 col=3
row=12 col=6
row=12 col=9
	in rectangle
	left side is 7
	right side is 11
	top side is 10
	bottom side is 14

[NetSpace]

а прямоугольник обязательно должен быть строго вертикальным или горизонтальным?
а если это всё же будет ромб или параллелограмм, т.е. проверку углов на соответствие 90 градусам надо делать?

[cllc]

Бонжур а ту лё монд
А то вот есть ещё такой "алгоритм":
1. Находим потенциальные углы (лев. верхн., лев. нижн., прав. верхн., прав. нижн.)
1а. Заносим их в отдельные списки.
2. Находим соответствующие координаты,
2а. попутно выбрасывая слишком мелкие прямоугольники.
2б. Добавляем координаты годных прямоугольников в список.
3. Фильтруем список от лишних прямоугольников (накладывающихся, залитых чернотой).
Получаем примерно такой результат:
19 rects
9 : 18 : 278 : 84 | 274 : 356 : 302 : 372 | 277 : 379 : 351 : 459 | 274 : 573 : 302 : 590 | 277 : 598 : 351 : 677 | 274 : 761 : 302 : 777 | 275 : 785 : 353 : 863 | 273 : 867 : 288 : 882 | 274 : 986 : 302 : 1002 | 274 : 1013 : 354 : 1030 | 446 : 574 : 580 : 591 | 445 : 987 : 579 : 1003 | 507 : 351 : 526 : 371 | 514 : 756 : 533 : 776 | 634 : 569 : 653 : 588 | 675 : 981 : 694 : 1000 | 1424 : 924 : 1551 : 951 | 1520 : 725 : 1551 : 752 | 1911 : 223 : 1917 : 1023 |
Картинка с найденными залитыми прямоугольниками

[Pcrepair]

DeepFlake, спасибо за алгоритм, попробую перевести на делфи

NetSpace, проверку углов на соответствие 90 градусам НЕ надо делать, там есть реальные прямоугольники и всякие многоугольники. но это не важно. есть еще тессеракт для символов, оно поможет отсеять не нужное

[Pcrepair]

Сообщение от cllc

1. Находим потенциальные углы (лев. верхн., лев. нижн., прав. верхн., прав. нижн.)
1а. Заносим их в отдельные списки.

вот тут если можно подробно. вопрос как раз об этом

[DeepFlake]

to Pcrepair:
в примерном изображении много одиночных белых точек (шума), я предлагаю фильтрациию так сделать: сначала перевести изображение в формат градаций серого, потом размыть изображение, то есть всё изображение разбить на квадраты 2х2 пиксела и усреднить в них цвет. Так исчезнут одиночные точки. Потом применить фильтр "резкость", потом перевести в монохромное изображение.

[cllc]

Сообщение от Pcrepair

вот тут если можно подробно. вопрос как раз об этом

Ну, как... Перебираем все точки, смотрим не являются ли они углами, например у левого верхнего угла, кот. белый пиксель, слева и сверху будут черные пиксели (тут же можно фильтровать одиночные пиксели) и т. д., и заносим их все в TList. ... А, дошло. Вам нужно чисто практически, как перебрать все пиксели. Код во вложении, тогда.

[DeepFlake]

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

С этим алгоритмом возникли такие сложности: во-первых, у некторых прямоугольников углы закруглённые, и если точка сетки попала на край прямоугольника, то обнаруживается граница прямоугольника только до начала закругления угла, а не до самой границы. Эта проблема решается путём объединения нескольких найденных областей в одну. То есть из нескольких точек сетки будут найдены области прямоугольника, и потом они объединяются.
Вторая проблема - прямоугольники в виде рамки, то есть у них внутри цвет чёрный. Эта проблема решается путём проверки цвета в середине найденного прямоугольника.

Программа на Java, у меня нет Delphi.