Привет,

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

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

Собственно задача выполнить сжатие этим методом максимально эффективно(минимальным количеством указания цвета). Тоесть если у нас к примеру 3 точки Черная, Белая, Черная. То у нас есть два варианта по очереди описать все три точки(это 3 указания цвета) либо задать глобально черный цвет а для белой точки переопределить его(это всего 2 указания цвета).
Первое что мне пришло на ум это построить бинарное дерево и на каждой ветке определять самый часто встречаемый цвет. Но это явно не самый эффективный алгоритм. Сдесь должно быть что-то адаптивное...

Если у вас есть какие-то идеи буду очень признателен! Спасибо!

PS: Еще раз напомню. Критерий эффективности: количество указаний цвета(чем меньше тем лучше).

Это сообщение отредактировал(а) SwordOfDeath - 7.2.2012, 23:28

Так смысла сжимать нет. 14 строчек против 10. По байтно сэкономили 10 байт потратили 24 дополнительных

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

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

PS. Если честно то я даже не понял вашу арифметику...
Если втупую определять цвет для каждой точки получим вот такое вот:


Это сообщение отредактировал(а) SwordOfDeath - 8.2.2012, 06:48

Отсортировать точки по цвету, очевидно, после чего указывать один цвет для каждой подряд идущей группы. Это будет абсолютно минимальный вариант: ведь каждый существующий в картинке цвет должэн быть указан, а здесь он будет указан ровно один раз.

tzirechnoy, он имеет в виду, что

эффективнее, чем


SwordOfDeath, а существует ли возможность задания повторяющейся группы? типа



декодируемого в 10-пиксельную группу БЧЧЧББЧЧЧБ ?

В том то и проблема... сами пиксели нужно указать полностью... 100х100 картинка будет иметь 10000 пикселей... Пиксели нельзя менять местами... они идут слева направо, сверху вниз... тоесть просто подряд...
Единственный метод сжатия который я могу применить это указание цвета групе пикселей с возможностью вложености(в таком случае цвет переопределяется). Структура очень похожа на XML...

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


Это сообщение отредактировал(а) SwordOfDeath - 8.2.2012, 18:36

SwordOfDeath, понял. 

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

Когда появляется очередной открывающий тег? когда меняется цвет (будем считать, что мы имеем дело с потоком, а не с матрицей). Можем мы на них сэкономить? только за счёт восстановления предыдущего цвета.
Когда появляется очередной закрывающий тег? когда мы завершаем вложенный одноцветный блок. Можем мы на них сэкономить? нет, их будет ровно столько, сколько открывающих.

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

Akina, 
Мой алгоритм всегда дает результат лучше чем если бы я напрямую  оборачивал абсолютно все группы пикселей(каждую своим цветом).
То что вы предлагаете с разделением это все верно... можно создать рекурсивный алгоритм который будет делить все пространсво на 2 части и для каждого из них определял самый еффективный цвет. Это пожалуй максимум что я смог придумать пока. Но это просто бинарное дерево, а хочется чего-то адаптивного, как вы и предлагаете... только я пока так ничего и не придумал...

Благодарен за внимание...

PS Это действительно лучше рассматривать как поток. Формат проходит верификацию(скорее всего каким-то xml парсером) так что все елементы должны быть правильно открыты и закрыты, не допускается пересечение (<a><b></a></b>). Все возможные варианты хитростей я уже рассмотрел... = )
PPS Форум что-то падает постоянно... 

ПРЕДЛАГАЕТСЯ СРАВНЕНИЕ НЕСКОЛЬКИХ МЕТОДОВ
Рассматривать будем картинки, после операции фильтрации, заменившей все подряд идущие пиксели одного цвета на один пиксел.
Введем некоторые обозначения
N – число смен цветов в картинке. Самая тупая оценка – N установок цвета.
Метод обрамления самым распространенным цветом среди групп. Оценка качества N-k+1, где k – число групп самого распространенного цвета.
Для определения максимально возможного сжатия используем метод глобального поиска минимума. Он NP полный (оценка порядка 2^N).
Как следствие предлагается использовать длину картинки порядка 100 (моя машина на больших размерностях не потянет).
Чисто поточный метод. Идея состоит в том, что при поступлении очередного пикселя определяется, есть ли он в стеке установленный на данный момент цветов, и, если есть, производится сброс до этого цвета, иначе – установка его в стек. Метод очень скоростной, но не самый лучший (качество его работы видно в статистике в приложенном файле). Оценка трудозатрат – N.
Оконно-поточный метод. Комбинация двух методов. Задаем ширину окна, равную n. Поток режется на куски по n элементов. Производится оптимизация кодирования в окне. Для каждого окна параметрами являются – набор пикселей и ранее сформированный стек. Оценка трудозатрат на этот метод равна (N/n)*2^n. Очевидно, что при n=N он дает глобальный поиск, а при n=1 – чисто поточный.
Сравнение строилось на картинках длиной в 50 пикселей, полученных случайной генерацией. Число цветов в картинках варьировалось от 5 до 20 с шагом 5.
Размер n варьировался от 5 до N/2 c шагом в 5
Из статистики видно, что при n=N/2 результат почти всегда тот же, а трудозатраты на несколько порядков меньше. Трудозатраты измерены в попугаях – числе вызовов процедуры выбора варианта продолжения.
Далее дело Вашего выбора что важнее – степень сжатия или время.

Приложенный код довольно странный, но писался для себя


Присоединённый файл ( Кол-во скачиваний: 1 )
 stat.rar 3,17 Kb

Mirkes,
Простите за поздний ответ, компьютер накрылся...

Я в джаве не очень, да и с алгоритмами тоже слабо дружу... А вы я смотрю изучали алгоритмы, видимо поэтому мне сложно понять вашу мысль )

Я так понял вы предлагаете просто в лоб(перебором) подбирать самый еффективный вариант растановки цветов, а для снижения сложности предлагаете выполнять перебор только по определенному окну?
Насколько я понял ваш метод вы протестировали на потоке из 100 пикселей? Тогда у нас беда... так как задача сделать это на ~10тыс. пикселей(100х100).
Хотя соглашусь что ваш метод на данный момент решает задачу полностью... Но сложность слишком высока.

PS Огромное спасибо за код... немного посмотрю как это на джаве выглядит. Свой алгоритм пишу на С++.

Это сообщение отредактировал(а) SwordOfDeath - 14.2.2012, 23:11

К сожалению я не дружу с С :(
В своем посте я рассмотрел три алгоритма.
Ниже я привел описание трех предложенных алгоритмов на псевдокоде, полученном из дикой смести C,Java,Pascal и 1С )

Для подсчета трудоемкости использкем следующие обозначения:
m - число групп пикселов одного цвета, идущих подряд. (если пикселы 1123331 то будет четыре группы 1231)
n - ширина окна для кодирования.
Stack - стек включенных на данный момент цветов
d - текущая глубина стека.
Est - текущее количество включений цвета.
Min - Текущий минимум включений цвета для полного кода
Code - массив для записи процедуры кодирования
BestCode - массив с записью лучшего кода
Pic - массив номеров цветов групп

Задача в исходной постановке является плохой - то есть NP полной.
Метод 1
Перебираем все возможные варианты.
s=0
Est=0
Min=10000000
Find(0)
Процедура Find(int j)
Если Est=Min Тогда
   Возврат - уже сделано столько же открытий, как в учшем варианте, а еще не все. Точно будет хуже, можно не смотреть.
Конец Если
Если j=m тогда
  Это полный код.
  Если Min>Est тогда
     Новый минимум найден.
     Min=Est
     BestCode=Code
  Конец если 
  Возврат
КонецЕсли
//Пытаемся получить цвет закрытием одного или нескольких цветов
Ищем наибольший номер k элемента стека с цветом Pic[j]
Если нашли тогда 
  Code[j]=d-k+1 (Плюс 1 в моей реализации. По сути нужно указать число ранее открытых цветов, которые следует закрыть)
  d=k
  Find[j+1]
  Восстанавливаем стек по массиву Code. Может есть смысл перед обработкой создавать копию стека - не знаю. Таких копий может потребоваться много.
Конец если
//Получаем цвет открытием цвета
Est=Est+1    еще одно открытие группы
Code[j]=Pic[j]
Find(j+1)
Est=Est-1    готовимся к откату
Конец процедуры

Достоинство метода - гарантированно найдет минимум
Недостаток - в худшем варианте 2^m вариантов при m=10000 это что-то около 10^300 вариантов, то есть бесконечно много

Метод 2
Строим максимально быстро
Идея метода примитивна и проста.
For i=0 To m-1 Do 
  Если в стеке есть цвет Pic[i] тогда
    Code[i]=d-k+1 (Плюс 1 в моей реализации. По сути нужно указать число ранее открытых цветов, которые следует закрыть)
    d=k
  Иначе
    Est=Est+1    еще одно открытие группы
    Code[i]=Pic[i]
  Конец если
Конец цикла

Достоинство метода - просмотр всего одной цепочки
Недостаток - чаще всего решение далеко от оптимального

Метод 3
Оконный метод
Потребуется еще пара переменных - 
Last - текущий конец просматриваемого участка
Start - текущее начало просматриваемого участка


s=0
Est=0
Last = -1;
Цикл (он будет с постусловием!)
   Start=Last+1
   Last=Last+n   // конец окна, для которого будем работать
   Если Last>m тогда
      Last=m
   Конец если
   Min=10000000
   Find(Start)
   Code=BestCode (восстанавливаем лучший код начального участка для продолжения)
   Est=Min
   Восстанавливаем стек по массиву Code. Может есть смысл перед обработкой создавать копию стека - не знаю. Таких копий может потребоваться много.
Конец цикла если Last=m

Процедура Find(int j)
Если Est=Min Тогда
   Возврат - уже сделано столько же открытий, как в учшем варианте, а еще не все. Точно будет хуже, можно не смотреть.
Конец Если
Если j=Last тогда
  Это полный код.
  Если Min>Est тогда
     Новый минимум найден.
     Min=Est
     BestCode=Code
  Конец если 
  Возврат
КонецЕсли
//Пытаемся получить цвет закрытием одного или нескольких цветов
Ищем наибольший номер k элемента стека с цветом Pic[j]
Если нашли тогда 
  Code[j]=d-k+1 (Плюс 1 в моей реализации. По сути нужно указать число ранее открытых цветов, которые следует закрыть)
  d=k
  Find[j+1]
  Восстанавливаем стек по массиву Code. Может есть смысл перед обработкой создавать копию стека - не знаю. Таких копий может потребоваться много.
Конец если
//Получаем цвет открытием цвета
Est=Est+1    еще одно открытие группы
Code[j]=Pic[j]
Find(j+1)
Est=Est-1    готовимся к откату
Конец процедуры

Достоинство метода - по времени он промежуточный. В худшем случае число просматриваемых вариантов порядка (m/n)*n^2
Недостаток метода - он часто дает не оптимальные решения, но они много лучше чем у второго метода.

Сравнение методов
Метод      Трудозатраты     точность
1                  2^m                 Оптимальная
2                  1                      Паришивая
3                  (m/n)*2^n        Приемлемая

Пояснения
В проведенных мной экспериментах при малой длине окна результаты в половине случаев совпадали с глобальным минимумом
Но я экспериментировал при малых длинах.
Думаю Вам следует провести серию экспериментов на полных рисунках и выяснить при какой длине окна Вы получите приемлемую точность за разумное время.

Альтернативой предложенным методам может быть только набор эвристик. Типа комбинацию 121 кодировать как уст 1 уст 2 сборс 1.
Я не смог придумать чего-то более разумного, но вдруг Вы сможете. Удачи

Mirkes, 
Огромное спасибо, а я ведь даже и не мечтал о такой существенной помощи. Воистину благодарен! (плюсик поставил!)

Сейчас в голове крутится очень много всего, нужно как-то все это систематизировать. Как напишу алгоритм обязательно выложу сюда...