ПРЕДЛАГАЕТСЯ СРАВНЕНИЕ НЕСКОЛЬКИХ МЕТОДОВ
Рассматривать будем картинки, после операции фильтрации, заменившей все подряд идущие пиксели одного цвета на один пиксел.
Введем некоторые обозначения
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 результат почти всегда тот же, а трудозатраты на несколько порядков меньше. Трудозатраты измерены в попугаях – числе вызовов процедуры выбора варианта продолжения.
Далее дело Вашего выбора что важнее – степень сжатия или время.
Приложенный код довольно странный, но писался для себя
| Код |
import java.awt.Dimension;
import java.awt.GridBagConstraints;
import java.awt.GridBagLayout;
import java.awt.HeadlessException;
import java.awt.Insets;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JScrollPane;
import javax.swing.JSpinner;
import javax.swing.JTextPane;
import javax.swing.SpinnerNumberModel;
import javax.swing.SwingUtilities;
public class PictureCode extends JFrame implements ActionListener {
private JTextPane pic = new JTextPane();
private JTextPane res = new JTextPane();
private JSpinner colors = new JSpinner(new SpinnerNumberModel(50, 1, 200, 10));
private Random rnd = new Random();
private static final int picSize = 50;
private int[] wholePic = new int[picSize];
private int[] filterPic = new int[picSize + 1];
private int[] code = new int[picSize + 1];
private int[] stack = new int[picSize + 1];
private int[] bestCode = new int[picSize + 1];
private int min, minn, full, last,calls;
private int[] testPic =
{ 0, 2, 0, 4, 0, 4, 2, 0, 1, 2, 0, 1, 3, 0, 3, 4, 2, 0, 2, 3, 1, 4, 0, 2, 4, 2, 1, 3, 1, 4, 0, 1, 2, 0, 4, 3, 4, 1,
4, 1, 0, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 };
public PictureCode() throws HeadlessException {
super("Picture coder");
setLayout(new GridBagLayout());
Insets ins = new Insets(3, 3, 3, 3);
// JLabel lab = new JLabel("Number of colors");
getContentPane().add(new JLabel("Number of colors"),
new GridBagConstraints(0, 0, 1, 1, 0, 0, GridBagConstraints.CENTER,
GridBagConstraints.NONE, ins, 0, 0));
getContentPane().add(colors,
new GridBagConstraints(1, 0, 1, 1, 0, 0, GridBagConstraints.CENTER, GridBagConstraints.NONE,
ins, 0, 0));
JButton but = new JButton("Generate picture");
but.setActionCommand("gener");
but.addActionListener(this);
getContentPane().add(but,
new GridBagConstraints(0, 1, 2, 1, 0, 0, GridBagConstraints.CENTER, GridBagConstraints.HORIZONTAL,
ins, 0, 0));
but = new JButton("Total search");
but.setActionCommand("total");
but.addActionListener(this);
getContentPane().add(but,
new GridBagConstraints(0, 2, 2, 1, 0, 0, GridBagConstraints.CENTER, GridBagConstraints.HORIZONTAL,
ins, 0, 0));
but = new JButton("Statistica");
but.setActionCommand("statist");
but.addActionListener(this);
getContentPane().add(but,
new GridBagConstraints(0, 3, 2, 1, 0, 0, GridBagConstraints.CENTER, GridBagConstraints.HORIZONTAL,
ins, 0, 0));
but = new JButton("Special");
but.setActionCommand("spec");
but.addActionListener(this);
getContentPane().add(but,
new GridBagConstraints(0, 4, 2, 1, 0, 0, GridBagConstraints.CENTER, GridBagConstraints.HORIZONTAL,
ins, 0, 0));
getContentPane().add(new JLabel("Picture colors"),
new GridBagConstraints(2, 0, 1, 1, 0, 0, GridBagConstraints.CENTER,
GridBagConstraints.NONE, ins, 0, 0));
getContentPane().add(new JLabel("Result code"),
new GridBagConstraints(3, 0, 1, 1, 0, 0, GridBagConstraints.CENTER,
GridBagConstraints.NONE, ins, 0, 0));
getContentPane().add(new JScrollPane(pic),
new GridBagConstraints(2, 1, 1, 5, 1, 1, GridBagConstraints.CENTER, GridBagConstraints.BOTH,
ins, 0, 0));
getContentPane().add(new JScrollPane(res),
new GridBagConstraints(3, 1, 1, 5, 1, 1, GridBagConstraints.CENTER, GridBagConstraints.BOTH,
ins, 0, 0));
setMinimumSize(new Dimension(800, 300));
setLocationRelativeTo(null);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
public static void main(String[] args) {
SwingUtilities.invokeLater(new Runnable() {
public void run() {
new PictureCode().setVisible(true);
}
});
}
public void filter() {
int j = 0, k = -1;
for (int i = 0; i < picSize; i++)
if (wholePic[i] != k) {
k = wholePic[i];
filterPic[j++] = k;
}
filterPic[picSize] = j;
}
private void restoreStack(int ind) {
stack[picSize] = 0;
full=0;
for (int i = 0; i < ind; i++) {
if (code[i] < 0){
stack[picSize] += code[i];
}else{
stack[stack[picSize]++] = code[i];
full++;
}
}
}
private void find(int ind) {
// Cutter
// int n=0;
// for (int i=0;i<ind;i++)
// if (code[i]>=0)
// n++;
// System.out.println("n "+n+" full "+full+" ind "+ind);
// if (full!=n)
// System.exit(1);
calls++;
if (full >= min)
return;
// the end??
if (ind == last) {
// calc result
if (full < min) {
if (min == picSize)
minn = full;
min = full;
System.arraycopy(code, 0, bestCode, 0, picSize);
}
return;
}
// there exist in stack?
for (int i = stack[picSize] - 1; i >= 0; i--)
if (stack[i] == filterPic[ind]) {
code[ind] = i - stack[picSize] + 1;
stack[picSize] = i + 1;
find(ind + 1);
restoreStack(ind);
break;
}
// add to stack
stack[stack[picSize]++] = filterPic[ind];
code[ind] = filterPic[ind];
full++;
find(ind + 1);
full--;
}
public void totalFind() {
stack[0] = filterPic[0];
code[0] = filterPic[0];
stack[picSize] = 1;
min = picSize;
last = filterPic[picSize];
full = 1;
calls=0;
find(1);
}
public void windowFind(int width) {
stack[picSize] = 0;
bestCode[0] = filterPic[0];
full = 0;
last = 0;
int start = 0;
calls=0;
do {
last += width;
if (last > filterPic[picSize])
last = filterPic[picSize];
min = picSize;
System.arraycopy(bestCode, 0, code, 0, picSize);
restoreStack(start);
find(start);
start += width;
} while (last < filterPic[picSize]);
}
public void drawBestCode() {
for (int i = 0; i < filterPic[picSize]; i++) {
System.out.print("" + bestCode[i] + '\t');
}
System.out.println();
}
public void drawFilter() {
for (int i = 0; i < filterPic[picSize]; i++) {
System.out.print("" + filterPic[i] + '\t');
}
System.out.println();
}
public void restoreControl() {
int st = 0;
int err = 0;
int n = 0;
for (int i = 0; i < filterPic[picSize]; i++) {
if (bestCode[i] < 0) {
st += bestCode[i];
} else {
stack[st++] = bestCode[i];
n++;
}
if (filterPic[i] != stack[st - 1])
err++;
}
if (err > 0)
System.out.println("min\t" + n + "\terrors\t" + err);
}
@Override
public void actionPerformed(ActionEvent e) {
if ("gener".equals(e.getActionCommand())) {
String s = "";
int cols = ((SpinnerNumberModel)colors.getModel()).getNumber().intValue();
for (int i = 0; i < picSize; i++) {
wholePic[i] = rnd.nextInt(cols);
s += " " + wholePic[i];
}
pic.setText(s);
} else if ("total".equals(e.getActionCommand())) {
String s;
filter();
s = "After filtration " + filterPic[picSize] + '\n';
res.setText(s);
stack[0] = filterPic[0];
code[0] = filterPic[0];
stack[picSize] = 1;
min = picSize;
full = 1;
find(1);
s += "Total minimum " + min + " stream minimum " + minn + '\n';
for (int i = 0; i < filterPic[picSize]; i++)
s += " " + code[i];
res.setText(s);
} else if ("statist".equals(e.getActionCommand())) {
for (int cols = 5; cols < 25; cols += 5) { // number of color
for (int f = 0; f < 10; f++) { // number of test
// generation
for (int i = 0; i < picSize; i++) {
wholePic[i] = rnd.nextInt(cols);
}
// filtering
filter();
System.out.println("colors \t" + cols + "\ttest#\t" + f + "\tgroups num\t" + filterPic[picSize]);
// drawFilter();
totalFind();
System.out.println("total\t" + min + "\tstream\t" + minn+"\tcalls\t"+calls);
restoreControl();
// drawBestCode();
for (int width = 5; width <= picSize / 2; width += 5) {
windowFind(width);
System.out.println("width\t" + width + '\t' + min+"\tcalls\t"+calls);
restoreControl();
// drawBestCode();
}
}
}
} else if ("spec".equals(e.getActionCommand())) {
// copy testPic to wholePic
System.arraycopy(testPic, 0, wholePic, 0, picSize);
filter();
System.out.println("colors \t" + "5" + "\ttest#\t" + "2" + "\tgroups num\t" + filterPic[picSize]);
// drawFilter();
totalFind();
System.out.println("total\t" + min + "\tstream\t" + minn);
// drawBestCode();
for (int width = 5; width <= picSize / 2; width += 5) {
windowFind(width);
System.out.println("width\t" + width + '\t' + min);
// drawBestCode();
}
}
}
}
|
|
)
)