מרחקים אוקלידיים ומציאת גוונים דומים

מחבר:
בתאריך:

המטרה של המדריך היא למצוא התאמה בין מערכים של מספרים. בהתאמה זו ניתן להשתמש כדי למצוא מילים בעלות משמעות דומה בתוך מילון מילים, חברים פוטנציאליים ברשתות חברתיות או שידוך באתר הכרויות. התנאי למציאת ההתאמה הוא שניתן לקודד את התכונות באמצעות מערך של מספרים כדי שהמחשב יוכל לחשב את המרחק בין המערכים ולמצוא את ההתאמה הטובה ביותר. ההנחה היא שככל שהערך של זוג של מערכים הוא קרוב יותר כך הם דומים יותר.

האפליקציה אותה נפתח במדריך מוצאת גוונים דומים מתוך מאגר של גוונים אקראיים כאשר המשתמש לוחץ על אחד הגוונים. כך נראית האפליקציה בפעולה:

אפליקציה לאיתור גוונים דומים

השיטה לקידוד צבעים שבה נשתמש במדריך היא RGB שמחלקת כל גוון לשלושה ערוצים (R - אדום, G - ירוק, B - כחול), כשכל ערוץ מקבל מספר בין 0 ל-255. לדוגמה,

RGB = 0, 0, 0

הוא שחור כי אף ערוץ לא מקבל צבע, ולעומת זאת מצב שבו כל הערוצים מקבלים ערך מקסימלי הוא לבן:

RGB = 255, 255, 255

כך מקודדים את הצבע האדום:

RGB = 255, 0, 0

כך מקודדים כחול:

RGB = 0, 0, 255

ואפור נוצר ממצב שבו שלושת הערוצים מקבלים את אותו ערך מספרי:

RGB = 110, 110, 110

 

חישוב מרחק אוקלידי

כדי למצוא גוונים דומים נשתמש בשיטה שמחשבת מרחק אוקלידי.

המרחק בין שני מספרים הוא ההפרש בין שני המספרים. לדוגמה, ההפרש בין 2 ל-8 הוא 6 וגם 6- (תלוי אם מפחיתים 2 מ-8 או הפוך). וכדי לקבל ערך שתמיד יהיה חיובי נעלה את ההפרש בריבוע, ונוציא שורש. 6 בריבוע שווה 36, וגם 6- בריבוע הוא 36. ושורש של 36 הוא 6, שהוא ההפרש בערך מוחלט.

התרגיל של העלאה בריבוע ואז הוצאת השורש כדי לקבל מרחק מוחלט נראה יותר מדי עבודה כשאנחנו מטפלים בערכים בודדים (סקלרים), אבל הוא מסייע לנו כשאנחנו רוצים לחשב את המרחק עבור מערכים של מספרים. לדוגמה שני המערכים הבאים, שכל אחד מכיל 2 ערכים (x ו- y):

A = [1, 2]
B = [5, 10]

כדי לחשב את המרחק בין שני המערכים נחשב את ההפרש בין כל זוג של ערכים תואמים, נעלה בריבוע, נסכום את הריבועים, ונוציא שורש מהסכום, לפי הנוסחה הבאה:

הנוסחה הכללית לחישוב מרחק אוקלידי עבור שני מערכים

ואם זה מזכיר לכם את הנוסחה לחישוב אורך קו ישר התחום בין שתי נקודות, A ו-B, במישור אז הדמיון הוא לא מקרי. נוסחה זו מבוססת על משפט פיתוגרס לפיו "סכום שטחי הריבועים, הבנויים על הניצבים במשולש ישר-זווית, שווה לשטח הריבוע הבנוי על היתר".

כפי שניתן לחשב את המרחק בין זוג מערכים שמכילים שני ערכים (אם תרצו מרחק בין שתי נקודות במישור) ניתן לחשב את המרחק בין זוג מערכים שמכיל 3 ערכים או יותר.

אותנו מעניין מה המרחק בין מערכים המכילים שלושה ערכים R,G,B

לדוגמה, מה המרחק בין גוון שהקוד שלו הוא:

RGB1 = 1, 2, 3

לגוון שהקוד שלו הוא:

RGB2 = 4, 5, 6

נציב בנוסחה לצורך חישוב המרחק בין שני המערכים:

חישוב מרחק בין שני מערכים בעלי 3 איברים המערכים מייצגים צבעים שמקודדים בשיטת RGB

 

האפליקציה

ה-html כולל טבלה שלתוכה נדביק את הגוונים שהתוכנה תגריל באקראי.

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>Euclidean distance</title>
    <style>
    .rect{width:16px;height:16px;border:1px solid #eee;display:inline-block;margin-right:8px;}
    </style>
  </head>
  <body>
    <table>
      <thead>
        <th>Color</th>
        <th>RGB Code</th>
        <th>Action</th>
        <th>Most Similar</th>
      </thead>
    <tbody>
			
    </tbody>
  </table>
</body>
</html>

הפונקציה הבאה מייצרת מספרים אקראיים בטווח שנגדיר לה (במקרה שלנו 0 עד-255):

// Generate random number in a range
function randomIntFromInterval(min,max) {
  return Math.floor(Math.random()*(max-min+1)+min);
};

ניצור 100 גוונים אקראיים מקודדים ב-RGB בתוך לולאה ונאסוף אותם לתוך המערך colors:

var colors = [];
for(var i=0; i<100; i++){
  colors.push({'r': randomIntFromInterval(0,255), 'g': randomIntFromInterval(0,255), 'b': randomIntFromInterval(0,255)});
}

הלולאה הבאה מייצרת את השורות של הטבלה מהפריטים במערך colors:

var tbody = document.querySelector('tbody');
for (var i = 0; i < colors.length; i++) {
  var tr = document.createElement('tr');
		
  var rgbString = [colors[i].r, colors[i].g, colors[i].b].join(',');
		
  var rect = document.createElement('div');
  rect.className = 'rect';
  rect.style.backgroundColor = 'rgb(' + rgbString + ')';
		
  var td = document.createElement('td');
  td.appendChild(rect);
  tr.appendChild(td);
		
		
  var td = document.createElement('td');
  td.appendChild(document.createTextNode( rgbString ));
  tr.appendChild(td);
		
		
  var td = document.createElement('td');
  var btn = document.createElement('button');
  btn.setAttribute('id', 'btn' + i);
  btn.setAttribute('data-red', colors[i].r);
  btn.setAttribute('data-green', colors[i].g);
  btn.setAttribute('data-blue', colors[i].b);
  btn.setAttribute('data-counter', i);
  btn.innerHTML = 'Find similar';
  td.appendChild(btn);
  tr.appendChild(td);
		
		
  var td = document.createElement('td');
  tr.appendChild(td);
		
		
  tbody.appendChild(tr);
		
		
  document.querySelector('#btn'+i).addEventListener('click',function($event){
    $event.preventDefault();
			
    var btn = this;
			
    var r = this.getAttribute('data-red');
    var g = this.getAttribute('data-green');
    var b = this.getAttribute('data-blue');
		
    var rgb = {'r':r, 'g':g, 'b':b};
			
    var similarColors = findMatching(rgb);
			
    var tdSimilar = btn.parentNode.parentNode.children[3]; 
			
    for(var si = 0; si < 5; si++){
      var rgbString = [similarColors[si].code.r, similarColors[si].code.g, similarColors[si].code.b].join(',');
				
      var rect = document.createElement('div');
      rect.className = 'rect';
      rect.style.backgroundColor = 'rgb(' + rgbString + ')';
      tdSimilar.appendChild(document.createTextNode( rgbString ));
      tdSimilar.appendChild(rect);
    }
  });
}

בחלק האחרון של הקוד לעיל אנחנו מוסיפים מאזין על הכפתור, שלחיצה עליו לוקחת את הערכים של RGB שמקודדים בתוך הכפתור באמצעות data attributes אוסף אותם לאובייקט ששמו rgb, שאותו אנחנו שולחים למציאת התאמה באמצעות הפונקציה findMatching, שמייד נקודד אותה. את 5 התוצאות הדומות ביותר שמחזירה הפונקציה נדביק חזרה להמשך השורה.

הפונקציה findMatching עושה את ההתאמה בפועל, בואו נראה איך היא עובדת:

// Find the distance and sort by closeness
var similarColors = [];
function findMatching(rgb){
  similarColors = [];
		
  for (var i = 0; i < colors.length; i++) {
    var rDistanceSquared = Math.pow(rgb.r - colors[i].r, 2);
    var gDistanceSquared = Math.pow(rgb.g - colors[i].g, 2);
    var bDistanceSquared = Math.pow(rgb.b - colors[i].b, 2);
			
    var total = rDistanceSquared + gDistanceSquared + bDistanceSquared;
    var distance = Math.sqrt(total);
		    
    var item = {};
    item.code = colors[i];
    item.distance = distance;
			
    similarColors.push(item);
  }

  similarColors.sort(function(a, b) {
    return a.distance - b.distance;
  });

  return similarColors;
};

הפונקציה מחזירה את מערך כל הגוונים בטבלה מסודרים לפי מידת הקרבה שלהם לגוון שהפונקציה מקבלת כפרמטר. לשם כך, הפונקציה עוברת על כל אחד מהגוונים בטבלה ומחשבת עבור כל אחד את מידת הקרבה האוקלידית לגוון שהיא מקבלת בתור פרמטר. את ערכי החישוב היא אוספת לתוך המשתנה similarColors. הפונקציה sort ממיינת את המרחקים בסדר עולה.

תם ולא נשלם

במדריך השתמשנו במרחק אוקלידי כדי למצוא את מידת הקרבה בין מערכים של מספרים מפני שהשיטה מוכיחה את עצמה ומצליחה למצוא גוונים דומים. אבל זה לא תמיד המצב. במקרים אחרים קורלציה בשיטת Pearson יכולה לעשות את העבודה טוב יותר בגלל שהיא לא מתחשבת במרחק המוחלט אלא במידת ההתאמה הלינארית בין המשתנים. לדוגמה, ברשת חברתית המנסה להמליץ למשתמשים על חברים בעלי טעם דומה. אם חבר A נוהג לתת דירוגים שבין 4 ל-5 וחבר B נוהג לתת דירוגים שבין 2 ל-3. מדד Pearson יכול למצוא התאמה למרות שהערכים הם שונים כל עוד המגמה נשמרת (המוצרים המדורגים במקומות הגבוהים והנמוכים של A דומים מספיק למוצרים המדורגים במקומות הגבוהים והנמוכים אצל B).

לכל המדריכים JavaScript למתקדמים

 

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים

 

 

הוסף תגובה חדשה

 

= 9 + 5