прореживание данных

А что такое "проредить"? Нечто по аналогии с "прополоть"?

int data[size];
double ratio=5.13;
int out[size/ratio];
unsigned double index=0;
unsigned int i=0;
while(index<size)
{
out[i++]=data[index];
index+=ratio;
}

элементы массива надо сажать друг от друга на расстоянии не менее 30 см. Это позволяет получать плоды быстрее и более высокого качества.

а теперь попробуй скомпилировать.

Первую версию я не компилял, навскидку написал чтобы проиллюстировать идею. Вот так пашет:

int size=512;
int data[size];
double ratio=5.13;
int out[(int)(size/ratio)];
double index=0;
unsigned int i=0;
while(index<size)
{
out[i++]=data[(int)index];
index+=ratio;
}

> Вот так пашет:

Оставляя в стороне телепатию (ибо что имел в виду автор под термином "прореживание данных", ведомо только ему), замечаем, что твоя программа запихнула 100 чисел в массив размером 99, и уменьшила размер не в 5.13 раз, а в 512.0 / 100.0 = 5.12 раз.

А что такое "проредить"? Нечто по аналогии с "прополоть"?

Децимировать :) с дробным коэффициентом. Хотя "прополоть" больше нравится )

> 2000 элементов проредить в 5.13 раз.

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

В зависимости от задачи. Например, если массив &mdash; это что-то типа рисунка или функции, то нужна интерполяция (самый простой способ nearest neighbour, но есть и более сложные и хорошие).

масштабирование одномерного растрового изоображения

>> int out[(int)(size/ratio)];

GCC'изм.

>масштабирование одномерного растрового изоображения

Собственно, это я и имел в виду, говоря об интерполяции.

>> int out[(int)(size/ratio)];

>GCC'изм.

Йа идиот, или это VLA?

>> Йа идиот, или это VLA?

WTF VLA?

> WTF VLA?

variable length array, C99

>> variable length array, C99

Хм... А я думал что это нестандартная возможность.

Сеёчас ещё нашёл, что в GCC оно не полностью и не совсем стандартно поддерживается (http://gcc.gnu.org/c99status.html):

Some details of variable length arrays (VLAs) relating to when size expressions are evaluated and when the memory for VLAs is freed are not implemented, and other details are not checked against the requirements of the C99 standard.

> ...самый простой способ nearest neighbour...

Даже поднапрягшись, не понимаю, как nearest neighbour interpolation алгоритм сязан с "прореживанием" -- типа, после интерполяции точек должно быть меньше в заданное кол-во раз? Один хрен, "2000 элементов проредить в 5.13 раз" в этом смысле будет означать возможность создания массива из 200000/513 элементов, а двоек в 513 вообще нет: 513=19*9, однако!

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

for ((i=0; i < 20; i++)) do echo $i; done |perl -ne '(print, $i-=5.53) if $i++ >= 0;'

>Даже поднапрягшись, не понимаю, как nearest neighbour interpolation алгоритм сязан с "прореживанием"

Исходный массив 200 000 элементов. Результирующий массив int(200000/5.13)=38986 элементов.

out[i]=f(i*5.13), где f(x) - это как раз функция интерполяции.

Об этом проще думать, как о сжатии изображения.

Это -- из области телепатии. Я не знаю, что имел в виду топикстартер под "прореживанием", а на вопрос он не отвечает.

Означает ли это именно интерполяцию? Может, он занимается кодиованием, и спрашивает, при каких условиях возможно энтропийное сжатие массива из 2000 элементов в 5.13 раз?

Или автор вопроса спрашивал, как в заданном массиве занулить приблизительно 413/513 часть элементов (или как-то их отметить, как ненужные)?

Если даже он имеет в виду интерполяцию, то о чем конкретно он спрашивает? О методах интерполяции вообще, или о том, как nearest neighbour вылавливать, или еще о чем?

> Исходный массив 200 000 элементов. Результирующий массив int(200000/5.13)=38986 элементов.

А почему мы именно так округляем до целого 200000/5.13 ?

> out[i]=f(i*5.13), где f(x) - это как раз функция интерполяции.

Если мы "ближайшего соседа" так ловим, то к нашим услугам nearbyint, rint, ceil, floor, round, trunc -- какую выберем?

Как это не отвечаю ? См. выше.

> А что такое "проредить"? Нечто по аналогии с "прополоть"?

>> Децимировать :) с дробным коэффициентом. Хотя "прополоть" больше нравится )

Более подробно: имеем N-мерный массив данных, а обработать можем только N/m отсчетов, причем m может быть дробным. Необходимо, таким образом уменьшить исходный массив, чтоб потерять как можно меньше информации, т.е. децимировать с коэффициентом m. Дециматор (КИХ) лепить не хочется, вот и спрашиваю, может еще какие методы есть ?

>А почему мы именно так округляем до целого 200000/5.13 ?

Ну логичнее, наверное, было бы int(x+0.5), но в данном случае, мне кажется, это не имеет отношения к сути вопроса. Я думаю, здесь стоит спросить, как появился коэффициент 5.13. Если исходной предпосылкой было максимальное количество элементов, то ответ о выборе размера результирующего массива очевиден.

>Если мы "ближайшего соседа" так ловим, то к нашим услугам nearbyint, rint, ceil, floor, round, trunc -- какую выберем?

Если он ближайший, то нужно брать ближайший элемент массива, т.е. нормальное человеческое округление к ближайшему целому.

Про то, что имел в виду автор вопроса, см. выше.

А, так это терминология из обработки сигналов! Я с ней давно не сталкивался...

Лучше не прибегать к голой децимации, она сильно спектр корежит, (много информации потеряешь), а слепить простейший "интерполирующий" дециматор с фильтром.

Я б так сделал (обозначения в терминах языка C): искал для каждого выходного i-го элемента (int)round(i*m)-й входной и усреднял по данному элементу, а также по P предыдущим и Q последующим соседям, где P и Q подбираются экспериментально, в зависимости от спектра, особенно на границах. Чем больше P и Q, тем сильнее сглаживание. Можно, например, начинать с P=0 Q=(int)(m-1) слева, далее P=Q=(int)(m/2.0) до правой границы, а справа P=(int)(m-1) Q=0. Если P и Q будут больше, получишь заведомо сглаживающий фильтр, если меньше -- спектр может быть "разболтанным" по сравнению с оригинальным, вплоть до m (если m - целое) копий спектра при "голой" децимации Q=P=0. Если m дробное -- еще биения появятся.

То есть, идея, надеюсь, понятна? Для i-го выходного элемента out[i] находишь k=(int)round(i*m) входной in[k] и вычисляешь значение out[i]=(in[k-P]+in[k-p+1]+...+in[k]+in[k+1]+...+in[k+Q])/(P+Q+1)

> Лучше не прибегать к голой децимации

Вообще-то децимация _уже_ не предполагает тупое отбрасывание отсчетов. Это КИХ фильтр с необходимой ЧХ (собственно его ты и описал но с прямоугольной ИХ с коэф. 1/(P+Q+1)). Но у меня проблема несколько другая - я априори не знаю полосу сигнала, а следовательно и подобрать ЧХ дециматора не могу, т.е. задача передескритизации не стоит. Есть просто набор данных (пофиг каких) и чисто физически я не могу все их обработать, а нужно минимизировать потери инфы. Вот вариант интерполяции к ближнему соседу заинтересовал. Вот еще б xто-нить в этом духе.

> Вообще-то децимация _уже_ не предполагает тупое отбрасывание отсчетов.

Вопрос терминологический, но, как я помню, децимация -- именно операция отбрасывания отсчетов в банке фильтров. Чтобы спектр не колбасило, перед децимацией в банке фильтров обычно выполняется НЧ фильтрация.

На практике у меня опИсанный мной фильтр (кстати, не обязательно линейный, и не обязательно КИХ -- P и Q могут зависеть и от n, и от сигнала) хорошо работал, но я его использовал только для всяких численных интегро-дифференциальных преобразований. Если слишком сложно -- усредняй по двум соседям без самого центрального значения, а меньше уж никак ничего толкового не получится (у меня не получалось).

> Вопрос терминологический

Для ЦОС - однозначный )

> перед децимацией в банке фильтров обычно выполняется НЧ фильтрация

Зачем? Дециматор сам и есть НЧ фильтр. Можно ставить CIC, но это для бастрого сноса. А банк фильтров в терминологии ЦОС - это набор фильтров на разные частоты.

> Для ЦОС - однозначный )

Мне помнится, что различали децимацию и фильтры-дециматоры. Впрочем, я не спец.

>> перед децимацией в банке фильтров обычно выполняется НЧ фильтрация

> Зачем?

Навскидку (автоУРЛ на ЛОРе сожрет последнюю скобку):

http://ru.wikipedia.org/wiki/Децимация_(обработка_сигналов)

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

Что-то педивикия гонит ) Дело в том, что, если частота дискретизации Fd > 2*Fв (где, Fв - верхняя частота в спектре сигнала см. т. Котельникова), то мы "нахватаем" разных паразитных частот. Так вот дециматор, в терминах ЦОС, это и есть НЧ фильтр, который убирает и ненужные частоты, и oversampling, настроен на полосу Fв полезного сигнала. Другое дело, что, если Fd >> 2*Fв, то порядок децимирующего КИХ фильтра сильно возрастает. Поэтому пользуют или CIC, или каскадное включение НЧ дец. фильтров разных порядков. Так что можно сказать, что НЧ стоит перед НЧ и НЧ и.....

Алгоритм Брезенхема?

> Что-то педивикия гонит ) ...

Нет, я это и сам помню, это классика. Дециматор создает алиасинг с m копиями спектра. Поэтому до децимации из сигнала убирают все, что выше частоты Найквиста (которая в российской литературе связывается с именем Котельникова) выходного сигнала.

Кстати, тот фильтр, что я описАл, этим и занимается.