برش میانه ای ( به انگلیسی: median cut ) الگوریتمی برای یافتن نماینده هایی مناسب از یک مجموعه عناصر چند بعدی است که توسط پاول هکبرت ( Paul Heckbert ) در سال ۱۹۷۹ میلادی ابداع شد. این روش یک الگوریتم بازگشتی است و در هر مرحله داده ها را به دو دسته حول میانه بُعد با بزرگ ترین دامنه تغییرات تقسیم می کند و در پایان برای هر دسته نماینده ای مشخص می کند. [ ۱] برش میانی در حال حاضر پر استفاده ترین الگوریتم برای گسسته سازی رنگ است.
این الگوریتم به این شکل عمل می کند که در هر دسته ابتدا مولفه ای که دامنه تغییرات عناصر در آن از بقیه بزرگ تر است را پیدا کرده و داده ها را برحسب مقادیر در آن بُعد مرتب می کند. سپس با پیدا کردن میانه داده ها را به دو دسته قبل و بعد میانه تقسیم می کند. اگر هنوز تعداد دسته های ایجاد شده از تعداد مورد نظر کمتر بود این عملیات را بر روی هر دو دسته ایجاد شده تکرار می کند. در پایان معمولاً میانگین عناصر هر دسته را به عنوان نماینده آن دسته انتخاب می کنند.
معمولاً عناصر مجموعه را به شکل یک بردار در نظر می گیرند. در این صورت شبه کد الگوریتم به این شکل خواهد بود:
def median_cut ( array, reprsnt_num, step ) : if ( 2 ^ step> = reprsnt_num or array. length < = 1 ) : return # max_range_dim finds the dimension with max " range" idx = max_range_dim ( array ) # sort_by_nth_comp sorts array by comparing nth component in elements sorted_array = sort_by_nth_comp ( array, idx ) # merge two arrays return median_cut ( array, reprsnt_num, step + 1 ) + median_cut ( array, reprsnt_num, step + 1 ) تحلیل الگوریتم اگر n داده در فضای m بعدی داشته باشیم، درصورتی که در پیاده سازی این الگوریتم از مرتب سازی هرمی ( از O ( n l o g ( n ) ) ) استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم ( از O ( m n ) ) و ادغام لیست ها را در O ( n ) انجام دهیم، داریم: T ( n ) = { 1 , if n = k T ( n / 2 ) + T ( n / 2 ) + n log ( n ) + C m n , if n > k از قضیه اصلی واکاوی الگوریتم ها داریم که چون: f ( n ) = n log ( n ) + m n = Ω ( n log b a + ϵ ) = Ω ( n ) ⟹ T ( n ) = Θ ( f ( n ) ) یعنی: T ( n ) = Θ ( n ∗ ( log ( n ) + m ) ) ( معمولاً n از m بسیار بزرگ تر است ) در پیاده سازی این الگوریتم بازگشتی از پشته استفاده می شود پس بهتر است با توجه به حجم بزرگ داده ها، از مرتب سازی های بازگشتی صرف نظر کنیم. [ ۲] گسسته سازی رنگ با در نظر گرفتن رنگ ها به صورت RGB , عدد هر رنگ یک عدد ۸ بیتی از ۰ تا ۲۵۵ خواهد بود. پس تعداد رنگ های ممکن برابر 256 3 = 16777216 خواهد بود. اما می شود با استفاده از تعداد بسیار کمتری رنگ متفاوت، در بسیاری از تصاویر کیفیت مطلوب را به دست آورد. مسئله پیدا کردن این رنگ های پالت نسبتاً کوچک تر است. این تعداد بستگی به نوع نمایش دارد ولی در بسیاری از نمایشگرها ۲۵۶ انتخاب می شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین الگوریتم به این شکل عمل می کند که در هر دسته ابتدا مولفه ای که دامنه تغییرات عناصر در آن از بقیه بزرگ تر است را پیدا کرده و داده ها را برحسب مقادیر در آن بُعد مرتب می کند. سپس با پیدا کردن میانه داده ها را به دو دسته قبل و بعد میانه تقسیم می کند. اگر هنوز تعداد دسته های ایجاد شده از تعداد مورد نظر کمتر بود این عملیات را بر روی هر دو دسته ایجاد شده تکرار می کند. در پایان معمولاً میانگین عناصر هر دسته را به عنوان نماینده آن دسته انتخاب می کنند.
معمولاً عناصر مجموعه را به شکل یک بردار در نظر می گیرند. در این صورت شبه کد الگوریتم به این شکل خواهد بود:
def median_cut ( array, reprsnt_num, step ) : if ( 2 ^ step> = reprsnt_num or array. length < = 1 ) : return # max_range_dim finds the dimension with max " range" idx = max_range_dim ( array ) # sort_by_nth_comp sorts array by comparing nth component in elements sorted_array = sort_by_nth_comp ( array, idx ) # merge two arrays return median_cut ( array, reprsnt_num, step + 1 ) + median_cut ( array, reprsnt_num, step + 1 ) تحلیل الگوریتم اگر n داده در فضای m بعدی داشته باشیم، درصورتی که در پیاده سازی این الگوریتم از مرتب سازی هرمی ( از O ( n l o g ( n ) ) ) استفاده کنیم و در هر مرحله برای پیدا کردن مولفه با بیشتربن بازه، کمینه و بیشینه را برای هر مولفه بیابیم ( از O ( m n ) ) و ادغام لیست ها را در O ( n ) انجام دهیم، داریم: T ( n ) = { 1 , if n = k T ( n / 2 ) + T ( n / 2 ) + n log ( n ) + C m n , if n > k از قضیه اصلی واکاوی الگوریتم ها داریم که چون: f ( n ) = n log ( n ) + m n = Ω ( n log b a + ϵ ) = Ω ( n ) ⟹ T ( n ) = Θ ( f ( n ) ) یعنی: T ( n ) = Θ ( n ∗ ( log ( n ) + m ) ) ( معمولاً n از m بسیار بزرگ تر است ) در پیاده سازی این الگوریتم بازگشتی از پشته استفاده می شود پس بهتر است با توجه به حجم بزرگ داده ها، از مرتب سازی های بازگشتی صرف نظر کنیم. [ ۲] گسسته سازی رنگ با در نظر گرفتن رنگ ها به صورت RGB , عدد هر رنگ یک عدد ۸ بیتی از ۰ تا ۲۵۵ خواهد بود. پس تعداد رنگ های ممکن برابر 256 3 = 16777216 خواهد بود. اما می شود با استفاده از تعداد بسیار کمتری رنگ متفاوت، در بسیاری از تصاویر کیفیت مطلوب را به دست آورد. مسئله پیدا کردن این رنگ های پالت نسبتاً کوچک تر است. این تعداد بستگی به نوع نمایش دارد ولی در بسیاری از نمایشگرها ۲۵۶ انتخاب می شود.
wiki: برش میانی