اختلال پرلین

منظره ایجاد شده به کمک الگوریتم اختلال پرلین

اختلال پرلین نوعی از اختلالات گرادیان (متحرک) است که در تصاویر ایجاد شده توسط کامپیوتر برای ملایم کردن خروجی به کار می‌رود. اختلالات گرادیانی نوعی از اختلال است که عمدتاً به عنوان بافتار رویهٔ اصلی در تصاویر ایجاد شده توسط کامپیوتر به کار می‌روند.

تاریخچه

کن پرلین در سال ۱۹۸۳ برای حل مشکل مصنوعی بودن تصاویر ایجاد شده توسط کامپیوتر این الگوریتم را ارائه کرد تا به کمک آن تصاویر واقعی تر و ملایم تری را بتوان به دست آورد. او به‌طور رسمی اکتشافات خود را در مقاله‌ای تحت عنوان ترکیب کننده تصویر در کنفرانس سیگراف اعلام کرد.

این تابع ظاهری شبه تصادفی دارد اما با این وجود تمام جزئیات بصری آن هم اندازه می‌باشند. این ویژگی به ما کمک می‌کند تا به راحتی آن را کنترل کنیم. چندین نسخه از اختلالات پرلین در مقیاس‌های مختلف می‌توانند توسط یک رابطه ریاضی به تنوع زیادی از بافتارها تبدیل شوند. به عنوان مثال می‌توان به کمک آنها سطوح اشیاء، آتش، دود و ابرها را ایجاد نمود.

جزئیات الگوریتم

اختلال پرلین عمدتاً بر روی دو، سه و چهار بعد پیاده‌سازی می‌شود اما می‌توان آن را برای ابعاد بالاتر نیز پیاده نمود. توجه داشته باشید که در ابعاد بالاتر از دو برای تهیه تصویر باید زاویه دید خود را نیز تعیین کنیم. پیاده‌سازی الگوریتم سه مرحله اصلی دارد:

تهیه جدول (grid)

نخست یک صفحه را به یک جدول m × n تبدیل می‌کنیم و در هر راس یک بردار گرادیانی تصادفی n-بعدی با طول واحد رسم می‌کنیم. (به استثنای حالت یک بعدی که در آن تنها یک اسکالر بین -۱ و ۱ نسبت می‌دهیم) دقت کنید که طول واحد به معنای طول یک نمی‌باشد و بردارها می‌توانند هر طولی داشته باشند اما تمامی بردارها باید طول یکسان و واحدی داشته باشند. به تصویر زیر توجه کنید:

جدول اختلال پرلین

ضرب داخلی

برای پیدا کردن مقدار اختلال هر نقطه دلخواه، آن خانه از جدول را که نقطه مورد نظر در آن قرار دارد را می‌یابیم و مختصات گوشه‌های متناظر با آن خانه جدول را پیدا می‌کنیم. سپس بردارهای گرادیانی ای را که از این گوشه‌ها بیرون می‌آیند را یافته و آن‌ها را به ترتیب ذخیره می‌کنیم و مقدار ضرب داخلی آن‌ها در بردارهای انحراف (offset vectors) (پایین‌تر به توضیح آن‌ها می‌پردازیم) را محاسبه می‌کنیم. به جدول زیر توجه کنید:

نقطه ای درون جدول پرلین

حال بردارهای انحراف را محاسبه می‌کنیم. بردار انحراف، برداری است که از نقطه مورد نظر به گوشه‌های خانه ای که در آن قرار دارد کشیده می‌شود. برای روشن‌تر شدن موضوع به تصویر زیر نگاه کنید:

ترسیم بردارهای انحراف و محاسبه مقادیر ضرب داخلی آن‌ها با بردارهای گرادیانی متناظر

حال به ازای هر کنج، حاصل ضرب داخلی بردار گرادیان و بردار انحراف را محاسبه می‌کنیم. توجه داشته باشید که اگر نقطه مفروض دقیقاً روی خطوط آن خانه از جدولی که در آن قرار دارد باشد، حاصل ضرب داخلی دو بردار دقیقاً برابر صفر خواهد شد.

الگوریتم پرلین نویز پیش از درونیابی

خروجی تصویری از طریق اعمال مقدار اختلال بر روی دو رنگ متفاوت به دست می‌آید. با توجه به مثبت یا منفی بودن مقدار اختلال، آن را بر روی یکی از رنگ‌ها اعمال کرده و مقدار رنگی حاصل را در صفحه به پیکسل متناظر اختصاص می‌دهیم.

درونیابی

گام نهایی، درونیابی حاصل ضرب‌های داخلی هر خانه از جدول است که به کمک اینکار اختلالات به دست آمده را اندکی ملایم تر (smooth) می‌کنیم. به‌طور کلی $n^{2}$ مقدار داریم که باید به کمک تابعی که مشتق اول و احتمالاً مشتق دوم آن صفر است آن‌ها را درونیابی کنیم. برای درونیابی نقاط می‌توانید از توابع درونیابی مانند bilinear interpolation استفاده کنید. اینجا ما از تابع $f(t)=6t^{5}-15t^{4}+10t^{3}$ برای درونیابی استفاده کرده‌ایم. تصویر فوق پس از درونیابی مقدار اختلال هر نقطه به تصویر زیر تبدیل می‌شود:

اختلال پرلین پس از اعمال درونیابی

پیاده‌سازی الگوریتم

پیاده‌سازی الگوریتم پرلین نویز به زبان پایتون در کد زیر آورده شده‌است.

import random
import math
import numpy as np

class PerlinNoise:
    """ 2-D implementation of the Perlin noise algorithm """
    def __init__(self, m_, n_, unit):
        self.m = m_  # column
        self.n = n_  # row
        self.unit = unit  # length of vectors
        vectors_dictionary = dict()
        for i in range(self.n + 1):
            for j in range(self.m + 1):
                first_component, second_component = random.uniform(-1, 1), random.uniform(-1, 1)
                norm_of_vector = math.sqrt(pow(first_component, 2) + pow(second_component, 2))
                normed_vector = [first_component / norm_of_vector, second_component / norm_of_vector]
                vector = [normed_vector[0] * self.unit, normed_vector[1] * self.unit]
                vectors_dictionary[(i, j)] = np.array(vector)
        self.gradient_vectors = vectors_dictionary

    @staticmethod
    def inner_product(first_vector, second_vector):
        return first_vector[0] * second_vector[0] + first_vector[1] * second_vector[1]

    def noise_calculator(self, coordinates):
        """ coordinates variable is the coordinates of the point that we want to calculate the value of noise in it. """
        x = coordinates[0]
        y = coordinates[1]
        adjacent_corners = [(int(x), int(y)), (int(x) + 1, int(y)), (int(x), int(y) + 1),
                            (int(x) + 1, int(y) + 1)]
        adjacent_vectors = [self.gradient_vectors[tuple(i)] for i in adjacent_corners]
        offset_vectors = [[int(x) - x, int(y) - y], [int(x + 1) - x, int(y) - y],
                          [int(x) - x, int(y) + 1 - y], [int(x) + 1 - x, int(y) + 1 - y]]
        p_1, p_2, p_3, p_4 = [PerlinNoise.inner_product(adjacent_vectors[i], offset_vectors[i]) for i in range(4)]

        def interpolator():

            def psi(t):
                return 6 * pow(t, 5) - 15 * pow(t, 4) + 10 * pow(t, 3)

            i, j = coordinates[0] - int(coordinates[0]), coordinates[1] - int(coordinates[1])

            return p_1 * psi(1 - i) * psi(1 - j) + p_2 * psi(i) * psi(1 - j) + p_3 * psi(1 - i) * psi(j) + p_4 * psi(i) * psi(j)
        return interpolator()

پیچیدگی

برای هر نقطه در جدول دو بعدی نیاز به محاسبه چهار بردار انحراف و در نتیجه چهار ضرب داخلی نیاز داریم. در جدول سه بعدی نیز به محاسبه هشت بردار انحراف و هشت ضرب داخلی باید بپردازیم. به‌طور کلی پیچیدگی زمانی این الگوریتم $O(2^{n})$ می‌باشد.

جستارهای وابسته

• برنامه‌نویسی
• پایتون
• الگوریتم
• تصویر مجازی