Sinclair Town #02 31 декабря 1994

Программирование

Начинающим - основные методы масштабирования изображения: Аппроксимация полутонами.

   АППРОКСИМАЦИЯ  ПОЛУТОНАМИ.

   Пусть  Вас  не  пугает данное
название.   Суть   этого  метода
очень проста.
   Еще при зарождении капиталис-
тического  строя  (  не  у нас в
России ) этот метод использовал-
ся  для изготовления текстильных
изделий.
   Что  же  это  такое  алгоритм
аппроксимации полутонами?

   Сначала    рассмотрим   метод
представления  информации, назы-
ваемый конфигурированием.
   Он  основан  на том, что нес-
колько  пикселей  объединяются в
конфигурации  ( обычно представ-
ляемые  в  виде  решеток, пример
см.  рис. 1 ). Далее все изобра-
жение  на  экране строится с ис-
пользованием  только данных кон-
фигураций точек.
   Для  примера, рассмотрим нес-
колько конфигураций ( квадратные
решетки  2*2,3*3,  прямоугольные
решетки 3*2 ).


 

 


   Нужно  выбирать  конфигурации
очень  осторожно,  так как иначе
могут  возникнуть  нежелательные
мелкомасштабные   структуры.  Не
стоит выбирать, например, струк-
туры типа горизонтальные линии и
типа  вертикальные линии. На ри-
сунке 2 показан пример неудачно-
го выбора конфигураций.
   Итак,  каждая  конфигурация (
решетка  ) состоит из определен-
ного числа пикселей и количество
пикселей   в  решетке  растет  с
вместе с уровнем интенсивности (
уровнем   закрашенности   данной
конфигурации).
   Причем,  при  размере решетки
M*N количество возможных уровней
интенсивности  равно  M*N+1,  и,
соответственно,  величина набора
конфигураций   будет  составлять
тоже M*N+1 конфигурацию.

   Это  все, что Вам нужно знать
о конфигурировании.
   Теперь   же  о  самом  методе
аппроксимации.  Итак, мы опреде-
ляем  (  можно  использовать уже
приведенные  методы  ) интенсив-
ность для каждой точки представ-
ляющей собой решетку 4*4 пикселя
(  для  экрана размерами: 128*96
точек,  для  набора конфигураций
2*2, либо 64*48 точек, для набо-
ра 4*4 ).
   После этого мы получаем соот-
ветствующую данной интенсивности
конфигурацию  точки ( к примеру,
используя пороговые значения ) и
изображаем ее на экране. Так об-
ходится весь экран.



 УЛУЧШЕНИЕ  ПОРОГОВЫХ МЕТОДОВ.

   Видно, что использование кон-
фигураций    ведет    к   потере
пространственного     разрешения
взамен   улучшения  визуального.
Можно  ли как-нибудь выбрать та-
кой  метод,  чтобы  получить ка-
кой-нибудь компромисс?
   Можно,  если использовать до-
работки  пороговых методов. Раз-
беремся в двух из них:

   А) Метод Флойда-Стейнберга;
   Б) Метод возбуждения;

   Рассмотрим их более подробно:

    МЕТОД ФЛОЙДА-СТЕЙНБЕРГА.

   При простом пороговом методе,
рассмотреном  в прошлом разделе,
наблюдается  потеря мелких дета-
лей  и фактуры слабого изображе-
ния.  Особенно  это  заметно для
волос  и складок одежды, а также
ее фактуры.
   Мелкие  детали теряются здесь
из-за  больших  ошибок выводимой
интенсивности для каждого пиксе-
ла.  То есть мы получали некото-
рую  общую  интенсивность  13, а
пороговое  значение для закраши-
вания  пикселя  у нас было 10. В
итоге мы получали ошибку  e= 13-
10   =   3.   В   методе   Флой-
да-Стейнберга  сама  эта  ошибка
распределяется   на   окружающие
пиксели  по закону, нарисованому
на рисунке 3. Таким образом, ес-
ли при обработке точки с коорди-
натами  (  0 , 0  )  мы получили
ошибку,   равную  8,  то  ошибка
распределенная  на точки с коор-
динатами  (  0 , 1 ) и ( 1 , 0 )
будет  равна 3, а на точку с ко-
ординатами ( 1 , 1 ) равна e= 2.
При  подсчете интенсивностей для
этих  точек к их общей интенсив-
ности  будет  добавлено значение
получившейся  ошибки.  Далее  мы
обрабатываем точку ( 0 , 1 ) по-
лучившуюся здесь ошибку для точ-
ки ( 1 , 1 ) мы прибавляем к по-
лучившейся ранее. И т.д.





   РИС.3 Распределение ошибки.

   Распределение ошибки улучшает
вид деталей изображения, так как
теряется только минимум информа-
ции.

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



       МЕТОД ВОЗБУЖДЕНИЯ.

   Этот  метод  не  требует  ве-
щественных  рассчетов  и наличия
буфера.  Было замечено, что если
в  изображение  вводится опреде-
ленный вид случайной ошибки, ко-
торая добавляется к общей интен-
сивности точки до ее сравнения с
пороговой  величиной, то изобра-
жение на экране улучшается.

   При этом добавление совершен-
но произвольной ошибки не приво-
дит   к  требуемому  результату.
Нужна матрица отвечающая следую-
щим требованиям:


 


   Получаются следущие матрицы:


              ┌     ┐
 размера 2*2: │ 0 2 │
(матрица Лима)│ 3 1 │(не из ф.)
              └     ┘

              ┌           ┐
 размера 4*4: │ 0  8  2 10│
              │12  4 14  6│
              │ 3 11  1  9│
              │15  7 13  5│
              └           ┘

   Далее эти матрицы в шахматном
порядке  добавляются к изображе-
нию.