Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Методы обхода плоскости

Задача обхода плоскости возникает при обработке двумерных данных. Цель: создание одномерного массива D из двумерного массива S. Причем если предполагается последующее сжатие D, то желательно создавать его так, чтобы "разрывов" было как можно меньше: каждый следующий эле­мент Д, заносимый в D на i-m шаге, является соседним (в плоскости) для предыдущего, занесенного в D на (/-1)-м шаге, Д./.

Змейка (зигзаг-сканирование)

Обход массива S начинается с одного угла плоскости, заканчивается в противоположном по диагонали. Например, из левого верхнего в правый нижний:

1

2

6

7

15

16

3

5

8

14

17

24

4

9

13

18

23

25

10

12

19

22

26

29

11

20

21

27

28

30

На иллюстрации показан порядок выборки элементов из плоскости (с последующим занесением в одномерный массив). Значение из ячейки массива S, помеченной на рисунке номером i, заносится в D[i].

Змейка выгодна в случаях, когда в одном из углов "особенность", на­пример сосредоточены самые крупные коэффициенты. Применяется в алго­ритме JPEG для обхода квадрантов (размером 8x8 точек).

Обход строками

Самый тривиальный метод. Именно он используется в самых распро­страненных графических форматах (BMP, TGA, RAS...) для хранения эле­ментов изображений.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

разв

оротг

1МИ Л

уы кг

1ЖД01

[ BTOI

борку в обратном направлении:

1

2

3

4

5

6

12

11

10

9

8

7

13

14

15

16

17

18

24

23

22

21

20

19

25

26

27

28

29

30

Точек "разрыва" нет, в отличие от варианта без разворотов. Совершенно аналогично можно делать обход столбцами.

Упражнение. Нарисуйте пример обхода плоскости столбцами с разворотами.

Обход полосами

Чаще всего сжатие лучше, если каждая область двумерного массива S не рассредоточена (равномерно "размазана") по всему одномерному D, а скон­центрирована в D компактно. В случае обхода строками понятие "области" отсутствует: каждый элемент считается "областью". Пытаясь обходить плоскость квадратами размером NxN, приходим к идее обхода горизонталь­ными "полосами" шириной N:

1

4

7

10

13

2

5

8

11

14

3

6

9

12

15

16

19

22

25

28

17

20

23

26

29

18

21

24

27

30

В данном примере ширина полосы N=3. Если N=1, получаем обход строками.

Полосами с разворотами

То же самое, но с разворотами и столбцов внутри полос, и направлений самих полос:

1

6

7

12

13

2

5

8

11

14

3

4

9

10

15

28

27

22

21

16

29

26

23

20

17

30

25

24

19

18

Разрывов опять нет, но теперь еще и каждая точка принадлежит к облас­ти, записанной в D компактно, без разрывов: ее элементы расположены внутри одного интервала (£>[/], /)[i+l], ■••, D[i+f\) и элементов из других об­ластей внутри этого интервала нет. Примеры таких областей - каждый из четырех углов размером 3x3 элемента.

Упражнение. Нарисуйте схему обхода квадрата 7x7 полосами шириной 3 с разворотами. Какой вариант лучше: 3+3+1 или 3+2+2? Какие области заносят­ся в D компактно?

Обход решетками

Для первой порции берем элементы из каждого N-ro столбца каждой М-й строки. Для второй - то же, но со сдвигом на один столбец. Так же и для следующих, а затем - со сдвигом на одну, две, (М-1) строки. Например, если M=N=2, то имеем 4 порции:

1

13

2

14

3

15

4

16

25

37

26

38

27

39

28

40

5

17

6

18

7

19

8

20

29

41

30

42

31

43

32

44

9

21

10

22

11

23

12

24

33

45

34

46

35

47

36

48

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

Обход решетками с учетом значений элементов

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

Допустим, атрибуты распределены так:

R

G

G

G

L

R

G

G

L

L

R

R

Тогда имеет смысл дальше действовать так:

R

13

G

25

G

28

G

31

15

14

27

26

30

29

33

32

L

40

R

16

G

34

G

37

42

41

18

17

36

35

39

38

L

43

L

46

R

19

R

22

45

44

48

47

21

20

24

23

То есть сначала обходим квадраты с атрибутом "R", затем с атрибутом "G" и, наконец, с "L".

Контурный обход

Часть элементов принадлежит к одной группе, часть - к другой, причем контур задан:

1

1

1

1

1

1

21

2:

1

1

2

21

М

2|

1

121

т

Я

т

й

1

1

ш

1

1

1

1

1

1

1

36 элементов - из группы "1", а 12 - из группы "2".

Очевидно, что имеет смысл отдельно оформить элементы группы "1"

1

29

28

27

26

22

21

31

2

30

25

23

20

32

3

24

19

33

4

18

34

5

8

9

13

14

17

35

6

7

10

И

12

15

16

36

и затем точно так же остальные элементы, принадлежащие к группе "2"

Контурный обход с неизвестными контурами

Рассмотрим предыдущий пример, т. е. такое же распределение элемен­тов групп по плоскости, но изначально, при начале обхода плоскости, это распределение неизвестно. Будем действовать таким методом:

1

44

41

40

35

34

29

28

2

43

42::.

39

36

33

30

27

3

45

46^

38

37 .-

32

31

26

4

ю :

47"

48

19;.

20

25

5

8

п

14

15

18

21

24

6

7

12

13

16

17

22

23

Обходим плоскость "столбцами с разворотами" и, обнаруживая элемент

другой группы (в элементах 9, 10, 14...), также делаем разворот на 180°. За­тем (шаги 45-48) обходим оставшуюся часть плоскости, содержащую (предположительно) элементы другой группы. В итоге имеем:

■ среди первых 36 элементов 4 из группы "2", а 32 из группы "1";

■ из последних 12 элементов 8 из группы "2", а 4 из группы" 1".

В первой части 4/36=1/9 "исключений", во второй - 4/12=1/3. А если бы делали просто обход "столбцами с разворотами":

1

12

13

24

25

36

37

48

2

11

.1*44

23г«

26

35

38

47

3

10-*.

15Ш

2*»

27JK

34

39

46

4

9 :&i

16-

21;;?

28»

ззе

40

45

5

8

17

20*

29

32

41

44

6

7

18

19

30

31

42

43

В итоге:

■ среди первых 33 элементов 12 из группы "2", а 21 из группы "1";

■ из последних 15 элементов все из группы" 1".

То есть в большей части получившегося блока - более чем 1/3 "исключений".

"Квадратная змейка"

Рекурсивный метод для квадратных областей.

Если принять левый верхний элемент за первый, то для квадрата 2x2 возможны два варианта обхода без разрывов:


1

4

2

3


1

2

4

3


То есть либо первый переход внутри квадрата был сверху вниз, тогда пя­тым шагом будет переход к левому верхнему элементу квадрата справа

(или к правому нижнему элементу квадрата сверху). Либо, наоборот, пер­вый переход внутри квадрата был вправо, тогда пятым шагом будет пере­ход к квадрату снизу (или слева). Переформулируем так:

если нужно выйти к правому (или верхнему) квадрату, то первый шаг -вниз, если к нижнему (или левому), то первый шаг - вправо;

пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

только в самом начале есть выбор одного из двух вариантов обхода. Например:




Первый шаг внутри квадрата 2x2 был вправо, - значит, в результате об­хода этого квадрата 2x2 мы должны выйти к нижнему квадрату 2x2.

Первый шаг перехода от 2x2 к 2x2 внутри 4x4 был вниз, - значит, мы должны выйти к правому 4x4.

Первый переход внутри квадрата 16x16 был вправо, - значит, в резуль­тате обхода 16x16 мы должны прийти к нижнему, и т. д.

Разрывов нет, и каждый элемент принадлежит к области, записанной компактно.

ЭД. Упражнение. Определите, какие числа должны быть в незаполненных клетках примера. Нарисуйте другой пример: при выборе второго элемента квадрата делаем переход не слева направо, а сверху вниз.

Для квадрата 3x3 можно взять такие два "шаблона":


1

4

5

2

3

6

9

8

7


1

2

9

4

3

8

5

6

7


Первое правило будет "противоположным" первому правилу случая 2x2, но остальные два - такие же:

если нужно выйти к правому (или верхнему) квадрату, то первый шаг - вправо, если к нижнему (или левому), то первый шаг - вниз;

■ пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

■ только в самом начале есть выбор одного из двух вариантов.

Но для 3x3 есть еще и такие варианты:


1

6

7

2

5

8

3

4

9


1

2

3

6

5

4

7

8

9


Видно, что они совершенно эквивалентны, т. е. взаимозаменяемы, по­скольку в обоих случаях мы выходим в правый нижний угол. Точно так же эквивалентны и два варианта обхода ими квадрата 9x9:

1

18

19

9

10

27

46

45

28

54

37

36

55

72

73

63

64

81


И


1

54

55

9

46

63

10

45

64

18

37

72

19

36

73

27

28

81


Совершенно аналогично для 5x5, и затем 25x25 и т. д.

Если требуется обойти квадрат размера NxN, сначала определяем, про­изведением каких простых чисел является N, затем задаем порядок этих чи­сел в произведении (а для каждого нечетного множителя еще и направление обхода). Таким образом будет задан процесс обхода.

Если К, равное числу двоек в произведении, больше одного: К>1, то сторона самого мелкого квадрата должна быть 2К"' или 2К элементов. На­пример, если К.=3, то обход без разрывов 2x3x2x2 (от самого мелкого 2x2 к 6x6, затем к 12x12 и, наконец, к 24x24) невозможен:

63

64

9

10

59

68

5

14

55

72

1

18

54

37

36

19

50

41

32

23

46

45

28

27

73

Каждая ячейка этой таблицы - квадрат 2x2; нижние 5 строк пропущены: перейти к двум нижним квадратам 12x12 без разрыва не сможем.

Других ограничений при обходе "квадратной змейкой" нет.

Каждый квадрат со стороной L>2 можно обходить обычной змейкой, а не "квадратной". Это выгодно в том случае, если наиболее различаю­щиеся элементы сгруппированы в противоположных углах квадрата.

S*. Упражнение. Нарисуйте порядок обхода квадрата 25x25, а затем - квадрата 12x12. Убедитесь, что разрывов нет и каждый элемент принадлежит к компакт­но записанной области.

Обход по спирали

Обход по спирали довольно тривиален. Строится квадрат 3x3, затем 5x5, затем 7x7,9x9 и т. д.:

43

44

45

46

47

48

49

42

21

22

23

24

25

26

41

20

7

8

9

10

27

40

19

6

1

2

11

28

39

18

5

4

3

12

29

38

17

16

15

14

13

30

37

36

35

34

33

32

31

Если же строить круги радиуса 2, 3,4 и т. д., неизбежно будут присутст­вовать точки разрыва. Спираль может быть и сходящейся. Суть ее можно показать с помощью этой же иллюстрации, только направление движения обратное: от 49 к 1. Кроме того, она может быть с разворотами:

1

2

3

4

5

6

7

24

25

40

39

38

37

8

23

26

41

42

43

36

9

22

27

48

49

44

35

10

21

28

47

46

45

34

11

20

29

30

31

32

33

12

19

18

17

16

15

14

13

Направление изменяется в точках, расположенных на диагонали: в дан­ном примере это "25" и "41".

Общие моменты для прямоугольных методов

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

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

Общие моменты для методов сложной формы

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