Блог

Главная - Вопросы по программированию - Как определить вычислительную сложность алгоритма обработки изображений

Как определить вычислительную сложность алгоритма обработки изображений

#algorithm #image-processing #video-processing #image-registration

#алгоритм #обработка изображений #обработка видео #регистрация изображений

Вопрос:

Я пытаюсь определить вычислительную сложность алгоритма в зависимости от количества пикселей, какой процедуре мне нужно следовать. Алгоритм основан на регистрации изображений.

Комментарии:

1. Пожалуйста, укажите алгоритм, о котором идет речь. Тогда мы сможем, по крайней мере, знать, о чем вы спрашиваете.

2. Алгоритм — это динамическое программирование для соответствия значению сходства характерных точек. и для алгоритма ransac с SIFT.

3. Опять же, это не очень конкретно. Отредактируйте свой вопрос, чтобы указать точный (минимальный) код, который выполняется.

Ответ №1:

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

например, этот алгоритм преобразует изображение в цвета сепии

 BufferedImage img = <input of the algorithm>
for(int i=0;i<img.getWidth();i  ){
    for(int j=0;j<img.getHeight();j  ){
        Color c = new Color(img.getRGB(i,j));
        double r = c.getRed();
        double g = c.getGreen();
        double b = c.getBlue();

        double r2 = 0.39 * r   0.76 * g   0.19 * b;
        double g2 = 0.34 * r   0.69 * g   0.17 * b;
        double b2 = 0.27 * r   0.53 * g   0.13 * b;
    }
}

Я вижу, что есть два цикла: один, который повторяется по ширине изображения, другой, который повторяется по высоте изображения.

Этот алгоритм посещает каждый пиксель один раз. Его сложность равна O (n), где n — количество пикселей во входном изображении.