powered by simpleCommunicator - 2.0.29     © 2024 Programmizd 02
Map
Форумы / Java [игнор отключен] [закрыт для гостей] / Кусочно линейная интерполяция с ограничениями
65 сообщений из 65, показаны все 3 страниц
Кусочно линейная интерполяция с ограничениями
    #40088638
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Привет.

Форк от другого топика Определить основной цвет фона.


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

Если точек будет 2 - то вообще отлично. На скетче я нарисовал оранжевым маркером то как я себе это вижу.

Спасибо.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088726
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Буду искать решение отдельно для каждого цветогово канала. Интерфейс может быть вида
Код: sql
1.
2.
3.
4.
5.
6.
7.
interface GradientOpmimizer {

    void init();

    Point[] optimize(double[] values, int maxPoints, double maxStandardDeviation);

}



здесь values - это входные значения уровней каналов RGB в порядке слева направо. Для простоты - нормированы в диапазон 0..1
maxPoints = 10 в данном кейсе
maxStandardDeviation - будем просто подбирать эмпирически. При слишком малом среднем отклонении
задача не будет иметь решений. При слишком большом - любой начальный расклад годится. Будем
просто искать серединку.

возвращаемое значение - массив вещественных точек Point(double,double) в порядке слева направо.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088826
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока смотрю в генетику. Если хромосома - это кусочно-линейная интерполяция (polyline) то
функция фитнеса - это standard deviation между графикой и полилинией.

Курю библиотеки jgap и jenetic но пока непонятно как сделать сложную хромосому. Они предлагают
то целочисленные то битовы то вещественные. Мне нужны координатные.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088928
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Читал-читал, ничего не понял.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088929
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Расчитай координаты оранжевой ломаной линии на рисунке.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088968
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Расчитай координаты оранжевой ломаной линии на рисунке.
Статистику я учил уже ооооочень давно и почти все позабыл. Тут лучше будет искать нынешних студентов и/или профессоров....

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

Берем десяток точек, строим на их основе "полосу доверия" (прямую с заранее заданным разрешенным отклонением) - пока отклонение от прямой не превышает некую величину продолжаем набирать новые точки. Если появилась подряд несколько новых точек ниже нижней границы полосы доверия, то перестаем считать их погрешностями и начинаем строить новую полосу доверия. Отходим чуть назад по точкам до последней точки с которой начался спад и считаем ее началом новой полосы доверия - строим новую полосу на основе нового десятка точек. И наоборот - новые точки выше полосы - отходим назад до центра полосы.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088969
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как в англоязычной литературе звучит эта "полоса доверия" ?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088982
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Как в англоязычной литературе звучит эта "полоса доверия" ?
Confidence level. Кажется... Давно учебник не читал.
Кажется по русски это будет "доверительный интервал"...

Суть в том что у тебя есть формула описывающая процесс в общем: y=f(x) . И ты знаешь что для всех y на участке а<x<b отличие рассчитанного y от фактического отличается не больше чем некоторая константа c . Соответственно "полоса доверия" это: f(x)-c < y < f(x)+c , где a<x<b .

Можно как вариант, сделать итеративный процесс - задаешь границы для x размером во всю выборку и считаешь для всех точек прямую ( y=kx ) а смещение по вертикали делаешь из расчета чтобы все точки попали в полосу доверия, потом сужаешь полосу (cокращаешь c ). Как появилась точка вне полосы - считаешь ее "поворотной", разбиваешь интервал определения x на две секции (по поворотной точке) и высчитываешь k отдельно для каждого участка и новые полосы по ширине считаешь по факту.
И повторяешь так до тех пор пока у тебя не получится набор полос с шириной не превышающей некое удобное для тебя значение и длиной не меньше чем сколько-то x .


хм... а ведь у нас архиватор с потерями получается.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40088988
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да. Это когнитивный архиватор. А термин доверительный интервал я помню. Что-то из статистики.

Спасибо. Это будет запасной вариант. Вариант Б если генетика не взлетит.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089028
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нарочно не вдаюсь в топик детально.
Что нарисовано для одномерной кривой может относиться
- к параметрической регрессии
- к линейным сплайнам
В любом случае имеются условяе стыковки отрезков.
Да, из задач оптимизации систем уравнений с многими переменными.
Сдругой стороны, при нек=х предположениях можно находить локальные вершины и низины методом слива уровня океана. Предварительно установив предельное кол-во островов и их диаметр. Это можно сразу на 2Д-поверхности.

Непонятно же главное: как это потом использовать. То есь для чего оно всё? От этого и надо танцевать.
Сбегал по ссылке в родительскую тему. Там неясно о чём: то ли о миниатюрах, то ли о компактном хранении ...
Надо уточнить.

Была фраза "узнаваемость". Есть сомнения, что линейный градиент сохранит узнаваемость. Особенно, если кривизна графика сильная. Глаз может путаться соценкой распределения оотенков перспективы. В жизни на сфере, здесь линейно - это меняет пропорции между регионами оттенков.

Была фраза "векторизация". Поэтому рискнул привести картинку с 10-уровневым оконтуриванием. Для простоты оконтуривал интенсивности.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089029
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дополню для одномерных графиков. Можно сначала несмещённо сгладить график, чтобы облегчить поиски мин/максов.
В 2Д можно ожидать, что число точек контуров много меньше площади рисунка. В 10-50 раз. Зависит от доли высоких частот в спектре фурье. На рисунке облачность разбивается на много мелких региончиков.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089086
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это investigation. Что получится в конце - пока не знаю. Возможно получится дизайнерский способ
хранить миниатюры. Как в конструктивизме. Вот заходите в картинную галлерею а там, конструктивисты
рисуют кубики и шарики. А в очертаниях вы угадываете людей.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089096
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98

Была фраза "узнаваемость". Есть сомнения, что линейный градиент сохранит узнаваемость. Особенно, если кривизна графика сильная. Глаз может путаться соценкой распределения оотенков перспективы. В жизни на сфере, здесь линейно - это меняет пропорции между регионами оттенков.


Линейный градиент - это 1-я итерация. На ней я планирую детектировать типичный фон для большинства
фотографий. Если фото будет снято с "заваленым" горизонтом - то мой метод потребует доработки. Нужен
будет виртуальный томограф чтобы понять куда смотрят основные линии.

2-я итерация - это детектирование "цветовых пятен" низкой частоты. Я долго думал как должны быть заданы
пятна - круговой градиент или просто круг. И пришел к выводу что круга вполне достаточно. Посмотрел
демо где портрет всем известной Лизаветы Джоконды апроксимируется набором цветовых пятен. Мне метод

[spoiler]
YouTube Video
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089105
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98

Была фраза "векторизация". Поэтому рискнул привести картинку с 10-уровневым оконтуриванием. Для простоты оконтуривал интенсивности.

Векторизация (трассировка) в чистом виде мне не нужна. (В) сегодня - это алгоритмически решенный вопрос
и для нее всегда можно найти и купить софт который сделает все что нужно в лучшем виде. Поэтому
спортивного интереса нет.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089107
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98

- к линейным сплайнам

Сплайны мне не подходят потому как градиент в SVG/JavaScript(Canvas API) не умеет задаваться в сплайнах.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089140
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
exp98

- к линейным сплайнам

Сплайны мне не подходят потому как градиент в SVG/JavaScript(Canvas API) не умеет задаваться в сплайнах.
А при этом топик спрашивает про кусочно-линейную ф-цию (ломанную), что и есть линейный сплайн. Если судить по картинке.

С желанием иметь основные фоны и цветовые пятна понятно, и это всего дело техники и времени.
С горизонтом не понятно всё, начиная с примера по ссылке.
В моём примере что горизонт? На картине "Мишки в лесу" что горизонт? Портрет/натюрморт в квартире? Снимок отражения в воде?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089142
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пока видятся 2 желания.
Выделять синтаксис, т.е. распределение регионов и оттенков. С этим проблем не видится.
Выделять семантику изображения. Напр., некий горизонт ??? Непонятна формулировка и как использовать.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089146
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Отражение в воде. Это не кроп. Это полный кадр. Снял для загадки.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089148
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не успел дописать самый первый свой вопрос.
Как понимать это: авторЕсли точек будет 2 - то вообще отлично. Отлично - ровно один отрезок? Ваще не проблема..
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089153
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

Это похоже на набережную Севастополя
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089154
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
)) Она и есть.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089155
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И всё же вопреки линейности, объявленной в теме. Почему косинус-преобр-ние не подходит (Фур.)? Там обычная схема.
Сначала сгладить палки спектра в боле-мене гладкую линию, потом выделять диапазоны или даже многокомпонентные кластеры частот. Именно низкие частоты дадут крупные пятна, правда те необязательно будут клмпактными.
Границы перепадов лежат в области в/ч. Туда попадёт чёткая линия горизонта, правда в обратную сторону неверно, но если объект крупный, то он не исчезнет при зуме.
Ну и т.д.....
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089159
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу кота. Если не брать особые художественные приёмы - то 99% информации о снимаемом объекте расположено
в центральной части картинки. Остальное по краям - это горизонт. Фон. Или посторонние объекты которые попадают
в кадр случайно (как в документальной съемке). Поэтому брать в распознавание надо центр. Остальное - можно
гнать через ФНЧ и этот 1% информации не окажет влияния на качество распознавания. Размер и пропорции
этой центральной части не важны. Когда я думал о горизонте - то я фактически предполагал полностью убрать
высокие частоты и оставить один цвет. Но можно и вертикальный градиент как наиболее популярный.
Впрочем это - опция.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089164
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, ну правильно, в центре. Потому что я снимал по правилам жанра "портрет". На троечку, но всё же. А недавно меня попросили щёлкнуть на смердофон т.ск. "на фоне зарослей". Пытался объяснить, что они будут на фото маленькими, а остальное займёт много места, уж лцчше тогда 3 разных зума и жанра. Ответили: пусть как будет. Заказчик - барин.
То есть не всегда большая часть, и не всегда даже по центру, и не всегда самое яркое.

Я не успел отредактировать предыд пост, но ты уже сказал про отделение "фона" и желаемых "объектов". Это уже семантика изображения. Ну и всё тот же Фур, наиболее мощные кластеры в области н/ч. Мощность=площадь под графиком.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089168
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня - ограниченный инструментарий по рендерингу векторной картинки. Вот посмотри.

Градиенты SVG.
https://developer.mozilla.org/ru/docs/Web/SVG/Tutorial/Gradients

Эллипсы SVG.
https://developer.mozilla.org/en-US/docs/Web/SVG/Element/ellipse

Что мне толку с Фурье если я не могу отрисовать синусоидный сигнал?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089204
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Про SVG я сразу поверил. Только не могу понять, как это связано с Ф.
Или речь идёт о восстановлении средствами обработчика изображений? Тогда ой!

Ну хорошо, пятна-кластеры,полученныеобратным Ф, заменить эллипсами. Мелкие почикать. Эллипсы -->SVG.
Ф - обратимое преобразование. При любых искажениях в спектре обратное Ф всегда что-то да выдаст. Если мало исказить, то и результат мало исказится. Мало по амплитуде, но конечно может по всему пространству рябь пойти.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089213
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Смотри.
1) Дана двумерная картинка.
2) Фильтруем ФНЧ по горизонтали с нулевой частотой. Получаем рябь в виде коротких градиентов или полосок как в ссылочном топике.
3) Далее - оптимизируем по размеру (нам ведь не нужно каждый пиксел делать градиентом). Из 200 градиентов делаем 10 (ну
в комбинации 3х каналов можем получить 30 штук).
4) Отрисовываем с помощью SVG или javaScrip/Canvas.
5) Получаем визуальный объект который достоверно отражает эту смазанную картинку вектором.

А где здесь мне полезно Фурье?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089226
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот еще интересный кейс. Здесь горизонт не завален. Но есть ярко выраженный
наклон низких частот на фоне.

...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089236
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
А где здесь мне полезно Фурье?
Так бы сразу и сказал(с)
И всё равно, фильтрация через Ф. гораздо гибче.
А с сохранением градиентов ещё прощебез "регрессий". Наложить 2Д-сетку и для каждой клетки подсчитать разницу суммы или среднего с 8-ю соседками. Дублирование встречным направлением исключить. И сетку можно ИТшную: 8х8 16х16 ...

Для просто узнаваемости даже достаточно из соседок выбрать максимальную. Цвета не сохранятся, но перпады контрастов отрисуют узнаваемый образ. Правда, я думаю, на тех снимках, где есть полутени от освещения, с мультиками может не прокатить. Да у меня и узнаваемый пример есть для 8х8. Если мня не погонят с форума, могу приложить, я заранее все персональные данные на рисунке отсёк. Ну что?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089250
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Наверное твой сеточный метод - это моя "мутация" в ГА
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089251
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Он не мой, он очевидный из простых. Вот сделал для снежного бугра, что был выше. 8х8, для монохрома.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089966
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Значит так. Где я застрял.

Есть 2 библиотеки. Jenetic и JGAP. Они - в состоянии решить мою задачу. Проблема - как всегда
в мелочах. А именно в следующем.

1) Мой искомый график == полилиния. С координатами вида (x1,y1),....(xn,yn).
2) Полилиния == Хромосома в терминилогии ГА. Ген - координата или цвет.
3) Фитнесс - функция == близость полилинии к исходному графику. А именно standard deviation.
4) Мутация. Здесь я завис. Мутацией может быть случайное смещение любой из координат в любую
сторону. А также случайное изменение цвета (яркость-насыщщеность-тон) в цветовой модели YUV.
Почему YUV лучше чем RGB в данной задаче - он лучше поддается человеческому визуальному восприятию
изменений. И я могу задать скажем мутацию в цветовом тоне в 10% а в яркости в 5%. За 1 шаг. В модели
RGB это было-бы невозможно.
Вобщем с мутацией сложно. +Цветовой тон завернут в кольцо.
Этим тоже можно воспользоватся в мутациях чтобы не было мертвых зон или таких областей в измерениях
где есть искажение распределения.

5) Крооссовером - или смешиванием хромосом-полилиний может быть просто заимстввание координат (или цветов).
Что именно или как - обобщенные библиотеки на которые я ссылаюсь просто умалчивают. В их
учебных tutorials они оперируют либо списком double / int / boolean а мне нужно более сложные
и более комплексные типы. Это самый сложный пункт по которому я ищу совета.

6) Поврежденные или запрещенные комбинации - это например когда x(n) > x(n + 1). На графике
это перекрученные 2 точки. Такого не бывает и я пока не знаю что с тамими делать? Делать их фитнесс
равным нулю ? Может быть. Подтвердите кто знает ГА.

7) Прочие вопросы. Как быстро сходится? Сколько ждать эпох? Итераций? Какой размер популяции?
Где можно срезать поворот? Подкинуть хромосому близкую к изначальному графику? Как близко?

8) Технические вопросы. Jenetic - полее новый и более продвинутый. Набит генериками. Но
не прост в осознании. JGAP - более старый. Но я пока не осилил реализовать мою полилинию ни там не там.

Линки на ресурсы:

Jenetic - https://jenetics.io/manual/manual-6.2.0.pdf
JGAP - https://sourceforge.net/projects/jgap/

Не будучи специалистом в ГА я просто надеюсь что эти библиотеки помогут решить задачу элегантно.
С "налёта и с нахрапа" не получилось. Буду рад вашим советам.

Линки на документы я чуть позже приаттачу если интересно. Хотя докумнетация по Jenetic достаточно хороша
и как теория.

2 Модераторы - прошу всё таки перенести этот топик в Java, поскольку я буду ссылаться на Java-specific
библиотечки. Спасибо.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089967
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Форк от другого топика Определить основной цвет фона.

Даны 3 серии чисел. По сути это цвета (RGB) одномерной картинки. Необходимо найти точки кусочно-линейной интерполяции
при условии что самих точек будет не много. Например не более 10 штук. Критерий - ... ну минимизация среднего кв.
отклонения.
Как-то это не производит впечатление удачного решения поставленной задачи.
Для сегментации обычно другие алгоритмы используются - кластеризация, анализ гистограмм...
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089968
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
То всё - узкие задачи. Не особо интересно.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089969
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
.... Критерий - ... ну минимизация среднего кв. отклонения....

Ну так и берем метод наименьших квадратов =)
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089970
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Он не описывает получение поли-линии.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089972
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Он не описывает получение поли-линии.
Как раз и описывает.
Может в вики это размыто написано
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40089998
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Необходимо найти точки кусочно-линейной интерполяции
при условии что самих точек будет не много. Например не более 10 штук.


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

Модератор: Тема перенесена из форума "Программирование".
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090021
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это внешний параметр (N). Я его задаю. Если задам 2 точки - будет регрессия всей функции
как предложил один господин выше.

Если точек больше - то алгоритм поиска приближения становится неоднозначным. Будет много
способов как расставить промежуточные точки. Линейная регрессия-же однозначна.

Я допускаю что мой метод не имеет единого
решения. Решений может быть бесконечное множество. Или решений не будет, если допуск
отклонения слишком мал и 10 точек недостаточно.

Итого.

Input:
Код: java
1.
2.
3.
N = 10
Standard Deviation = 1.0; //  (подбирается экспериментом)
F = [0.0029, 0.0027..... ] 



Output:
Код: java
1.
Polyline = [ (0.0, 0.002), (33.0, 0.002) ...... ]
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090068
mayton, мне кажется я уже писал об этом, но повторюсь - по-моему это неправильно называть интерполяцией. В моем понимании интерполяция находит точки между двумя известными точками. А ты же хочешь и известные точки заменить на что-то другое. В моем словаре это называется сглаживанием. Возможно если погуглить это как сглаживание, то и вариантов больше найдется.

И судя по твоем рисунку задача сводится к нахождению пиков:
1. Рисуем отрезок от начала пика до вершины
2. Рисует отрезок от вершины к окончанию пика
3. Рисуем отрезок до начала след пика

И если это так, то всю задачу можно переформулировать как:
1. Сгладить сигнал (чем больше сгладили - тем меньше пиков найдем)
2. Построить отрезки между вершинами и границами пиков

Не уверен правда что это облегчает тебе задачу, потому как нахождение пиков - это тоже не просто и опять же есть много вариантов :) Но если этот вариант подходит, то могу подсказать парочку алгоритмов которые использую в своей сфере.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090126
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да. Я думал про ФНЧ как про способ генерации первого приближения для этих точек.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090133
mad_nazgul
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

Т.е. нужно что-то вроде этого ?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090211
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Квадратные и кубические кривые тоже не решаеют моей проблемы. Т.к. рендеринг
изображения я буду делать все равно через градиенты. А это - линейные зависимости.

Тоесть любого вида кривые могут помочь мне сделать первые шаги алгоритма. А потом все
равно надо на этих кривых указать мои искомые 10 точек.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090642
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот удачный вариант. Кот сидит на фоне имеющем вид горизона.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090645
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Справа - оригинальное изображение. Слева я сделал последовательность 10 Rectangles и залил их градиентом
с фиксированным шагом. Здесь не было никаких аппроксимаций и не было претензий на численные методы
или генетический поиск удачной комбинации прямоугольников.

Но даже здесь видно насколько близко к оригиналу 10 плиток транслируют образ исходной фотографии.

Вот эти градиенты в текстовом представлении.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
(x,y,color) = (0,0,#878377)
(x,y,color) = (0,108,#868475)
(x,y,color) = (0,216,#858273)
(x,y,color) = (0,324,#7E7B6C)
(x,y,color) = (0,432,#8496AA)
(x,y,color) = (0,540,#BFC7D4)
(x,y,color) = (0,648,#E2D7C3)
(x,y,color) = (0,756,#C8B998)
(x,y,color) = (0,864,#F2E3CC)
(x,y,color) = (0,972,#E4D9BD)
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090648
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По традиции. Сорц.

Код: java
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.
31.
32.
33.
34.
35.
36.
37.
        BufferedImage source = ImageIO.read(new FileInputStream("......."));

        int SRCX = source.getWidth();
        int SRCY = source.getHeight();

        int FHDX = Resolutions.FULL_HD.x;
        int FHDY = Resolutions.FULL_HD.y;

        long t = System.currentTimeMillis();

        BufferedImage dest = new BufferedImage(FHDX, FHDY , BufferedImage.TYPE_INT_RGB);

        Graphics graphics = dest.getGraphics();
        Graphics2D g2 = (Graphics2D) graphics;

        int STEPS = 10;

        int srcStep = SRCY / STEPS;
        int srcY = 0;

        int step = FHDY / STEPS;
        int destY = 0;

        for(int i = 0; i < STEPS; i++) {
            srcY = (i * SRCY) / STEPS;
            destY = (i * FHDY) / STEPS;
            Color color = new Color(source.getRGB(0, srcY));
            GradientPaint blackToGray = new GradientPaint(
                    0, destY,        color,
                    0, destY + step, new Color(source.getRGB(0, Math.min(srcY + srcStep + 1, SRCY - 1))));

            g2.setPaint(blackToGray);
            g2.fill(new Rectangle2D.Double(0, destY, FHDX, step + 1));
            System.out.printf("(x,y,color) = (%d,%d,%s)\n", 0, destY, colorToWeb(color));
        }

        ImageIO.write(dest, "PNG", new FileOutputStream(".........."));

...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090650
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пипеткой были взяты цвета с левого бордюра фотографии с котом. Это - не совсем правильно.
Но в обобщённом варианте у меня будет взвешенное произведение поверхности имеющей
вид горки (Гаусс) на исходно изображение. Это даст больше весов границам и подавит центр.

На второй итерации я попробую поискать аппроксимацию картинки центра набором полу-прозрачных
цветных эллипсов. С учотом того что фон уже существует.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090651
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Вот удачный вариант. Кот сидит на фоне имеющем вид горизона.

хм.. Прикольно. Походит на фильтр Размытие примененное к фото.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090654
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из проблем. Для ГА алгоритма над которым я пока еще думаю будет большая проблема.
Это фитнес-функция для "эллипсов".

Если с градиентами я еще "пропетлял" свернув размерность от декартовой плоскости к вектору
то с эллипсами такой вариант - вообще не прокатит. Мне придется умножать картинку на картинку.
Это и будет фитнесс-величина.

Есть варианты - просто уменьшить разрешение картинки например в 4х или 8х раз для самых ранних
популяций хромосом но в самых последних решающих итерациях мне все равно придется
умножать FULL-HD (в пикселах) на такой-же эталон. Я вот думаю что если я развалю
картинку на 3 вектора типа

Код: java
1.
2.
3.
double[] r;
double[] g;
double[] b;


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

Василий анонсировал нам векторизацию в последних релизах JDK но как ее активировать и как ей
воспользоваться - ХЗ.

PetroNotC Sharp - ты слышал что нибудь про реализацию векторизации в JVM ?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090661
Я пробовал векторное API на своем проекте, очень надеялся что будет летать, но.. никакого прироста не было :) Видать автовекторизация в моем случае и так хорошо срабатывала.

Как вариант еще переход на float вместо double (если это допустимо) может ускорить работу.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090662
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
PetroNotC Sharp - ты слышал что нибудь про реализацию векторизации в JVM ?
я в этом нуб.
У меня хобби прикладной код и архитектура. То что "можно потрогать руками".
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090682
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stanislav Bashkyrtsev
Я пробовал векторное API на своем проекте, очень надеялся что будет летать, но.. никакого прироста не было :) Видать автовекторизация в моем случае и так хорошо срабатывала.

Как вариант еще переход на float вместо double (если это допустимо) может ускорить работу.

Да. Массив float - тоже хороший вариант. По крайней мере я не вижу доводов против.
Если это поможет векторизации.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090711
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Линки по теме.

Вот джеб.
От 2018 года https://openjdk.java.net/jeps/338
ОТ 2021 года https://openjdk.java.net/jeps/414

Вот господин с прозаичной фамилией Иванов вещает нам свое видение

YouTube Video
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090767
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На 17 минуте Иванов показывает что детектирование факта перехода на векторизацию возможно для
отладночных сборок. Это меня немного не устраивает. Это как работать с Ораклом и не видеть
результата применения хинтов кроме как по времени отклика. А само по себе время в JVM
- достаточно сложно измеримо. Нужен хороший прогрев и большая выборка измерений чтоб
доказать что векторизация сработала.

Альтернативный вариант - наблюдать дамп ассемблера через -XX:+PrintAssembly и просто ожидать там
соотв. инструкций.

Вообще чем больше я смотрю тем больше вижу что векторизация это очень малая часть стека которая мне реально
нужно.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090768
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Моя тренировочная база на сегодня.

Допустим я решил развалить RGB картинку в YUV представление и для наглядности изобразить ее в виде 4х
кадров - цветная и соотв 3 цветовых канала яркости и двух цвето-разностных. Как в телевидении Secam.

Интересующий меня фрагмент - пока крохотный и не занимает особого времени в вычислениях. (Пока).
Большую часть времени занимают чтение jpg файла и конверсия его в float представление.

Код: java
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.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
// 14-Aug, 2021 - mayton

public class YUVDecomposer {

    static Logger logger = LoggerFactory.getLogger(YUVDecomposer.class);

    public static void main(String[] args) throws IOException {
        // Convert from RGB to floating points quaternions
        String sourcePath = args[0];

        BufferedImage source = ImageIO.read(new FileInputStream(sourcePath));
        int W = source.getWidth();
        int H = source.getHeight();
        int PIXELS = W * H;

        logger.info("W = {}, H = {}, colorModel = {}", W, H, source.getColorModel());

        // 4 * sizeOf(float) = 4 * 32bit = 128bit. This is the same as single XMM register.

        float[] rgbSourceFloat = new float[PIXELS * 4];
        logger.info("rgbSourceFloat size = {}", rgbSourceFloat.length);

        // RGB ratios plane
        float[] yuvRatios = new float[PIXELS * 4];
        int i = 0;
        for (int j = 0; j < PIXELS; j++) {
            yuvRatios[i++] = (float) Constants.RK;
            yuvRatios[i++] = (float) Constants.GK;
            yuvRatios[i++] = (float) Constants.BK;
            yuvRatios[i++] = 0.0f; // Placeholder to be aligned
        }

        i = 0;
        int color = 0;
        for (int y = 0; y < H; y++) {
            for (int x = 0; x < W; x++) {
                color = source.getRGB(x, y);
                rgbSourceFloat[i++] = ImageUtils.getRPixel(color) / 255.0f; // Normalize to [0..1] range
                rgbSourceFloat[i++] = ImageUtils.getGPixel(color) / 255.0f;
                rgbSourceFloat[i++] = ImageUtils.getBPixel(color) / 255.0f;
                i++;
            }
        }

        // YUV-Plane
        float yval = 0.0f;
        float[] yPlane = new float[PIXELS];
        //float[] uPlane = new float[W * H];
        //float[] vPlane = new float[W * H];
        StopWatch renderYPlaneStopWatcher = StopWatch.createStarted();
        int j = 0;
        i = 0;
        // #pragma force jvm vectorization :)
        while (i < yuvRatios.length) {
            float yPlaneVal = 0.0f;
            // assumed mulps xmm0, xmm1 ... will be used
            yPlaneVal += yuvRatios[i] * rgbSourceFloat[i]; // Ri * RK
            i++;
            yPlaneVal += yuvRatios[i] * rgbSourceFloat[i]; // Gi * GK
            i++;
            yPlaneVal += yuvRatios[i] * rgbSourceFloat[i]; // Bi * Bk
            i++;
            yPlaneVal += yuvRatios[i] * rgbSourceFloat[i]; // Placeholder
            i++;
            yPlane[j] = yPlaneVal;
            j++;
        }
        renderYPlaneStopWatcher.stop();
        logger.info("renderYPlane : {} ms", renderYPlaneStopWatcher.getTime(TimeUnit.MILLISECONDS));
        // TODO: Render U, V
        
        // TODO: Generate U, V images

        // Export YUV planes as 4 split-screen images to be clear
        BufferedImage dest = new BufferedImage(W * 2, H * 2, BufferedImage.TYPE_INT_RGB);
        Graphics2D g2d = (Graphics2D) dest.getGraphics();
        ImageObserver imageObserver = new YUVImageObserver(); // TODO: WTF? How to sync with fucken image observer?
        g2d.drawImage(source, 0, 0, imageObserver);
        sleep(5 * 1000);
        
        // TODO: Place Y, U, V images into 2,3,4x splits

        ImageIO.write(dest, "PNG", new FileOutputStream(FileUtils.trimExtension(sourcePath) + "-YUV-4x-split.png"));



    }
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090769
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тренировочная JDK (предпоследняя на данный момент).
Код: java
1.
2.
3.
4.
5.
6.
7.
$ javac -version
javac 16.0.2

$ java -version
openjdk version "16.0.2" 2021-07-20
OpenJDK Runtime Environment (build 16.0.2+7-67)
OpenJDK 64-Bit Server VM (build 16.0.2+7-67, mixed mode, sharing)
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090770
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
22 милисекунды на умножение двух плоскостей. Для 3х мегапиксельной картинки. Достаточно быстро пока
чтобы я вообще не парился этим вопросом.

Код: java
1.
2.
3.
[main] [INFO ] W = 3850, H = 2539, colorModel = ColorModel: #pixelBits = 24 numComponents = 3 color space = java.awt.color.ICC_ColorSpace@6483f5ae transparency = 1 has alpha = false isAlphaPre = false
[main] [INFO ] rgbSourceFloat size = 39100600
[main] [INFO ] renderYPlane : 22 ms
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090771
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Косячок.

Кто знаток Swing-графики? Вот эта операция по идее асинхронная. И ее надо блочить то тех пор
пока observer не получит событие что обновление завершено.

Код: java
1.
g2d.drawImage
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090772
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
О. На 25 минуте Иванов показывает какие условия допустимы для unroll цикла. Переписал по аналогии.
Пускай шаг идет в 4 байта и offsets будут констанатами.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
        for (i = 0; i < yuvRatios.length; i+=4) {
            float yPlaneVal = 0.0f;
            // assumed mulps xmm0, xmm1 ... will be used
            yPlaneVal += yuvRatios[i+0] * rgbSourceFloat[i+0]; // Ri * RK
            yPlaneVal += yuvRatios[i+1] * rgbSourceFloat[i+1]; // Gi * GK
            yPlaneVal += yuvRatios[i+2] * rgbSourceFloat[i+2]; // Bi * Bk
            yPlaneVal += yuvRatios[i+3] * rgbSourceFloat[i+3]; // Placeholder
            yPlane[j] = yPlaneVal;
            j++;
        }



Время пока не изменилось.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Черт. Шаблон не множко не тот. Кто помнит в SSE есть такая инструкция чтоб взять 4 вещественных и перемножить на 4
других и просуммировать результирующий вектор?
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090777
maytonНа 17 минуте Иванов показывает что детектирование факта перехода на векторизацию возможно для
отладночных сборок.Это ты смотришь про автовекторизацию. А в 16ой появилась явная - там прям Java API для того чтоб самому писать векторизованный код. Только этот API в инкубаторе пока.

Но с такой простой математикой мне кажется у тебя должна была и автовекторизация включиться.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090842
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я пожалуй пока возьму паузу. Я кое-какие выводы для себя сделал. В. - это хорошая механика
но надо сначала делать прототип в обычном прямом виде и смотреть на В. лишь только после бенчмарков.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090895
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
забудьте про яву в контексте производительности. навсегда.

уже все опции выбраны, не полечило
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090910
забыл ник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Siemargl
забудьте про яву в контексте производительности. навсегда.

уже все опции выбраны, не полечило

Окей, теперь всё стало по своим местам.
...
Рейтинг: 0 / 0
Кусочно линейная интерполяция с ограничениями
    #40090913
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В первом приближении так. Пока без цвета. Только luma. Может я и дальше выкину расчет цвета из приближения.
Так узловых точек будет меньше.
...
Рейтинг: 0 / 0
65 сообщений из 65, показаны все 3 страниц
Форумы / Java [игнор отключен] [закрыт для гостей] / Кусочно линейная интерполяция с ограничениями
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]